Composing Turing Machines in FSM

on YouTube ↗26m

" summary

A domain-specific language called FSM DSL lets students define Turing machines, run unit tests, and compose machines with a small embedded language of sequencing, labels, conditional jumps and variable-binding. The demo builds primitives (move right, write/erase), composes R twice, implements head-scanning loops and a full adder for unary naturals, and executes examples live. Correctness is argued with Hoare-style triples and the implementation and examples are available on GitHub.

AI-written summary · about

" chapters (7)

1. 0:00Frustration with pen-and-paper TMs
2. 3:58Beyond simple Turing machines
3. 7:52Composing TMs with labels and jumps
4. 10:19Adding two numbers on a TM
5. 18:34Formal reasoning with Hoare logic
6. 18:55FSM textbook and resources
7. 19:57Group discussion