Turing Machine Simulator
Universal computation — any algorithm expressible as state transitions on an infinite tape
← infinite tape →
State
q0
Head Position
0
Steps
0
Status
Ready
Step
Run
Stop
Reset
Speed:
5 steps/frame
Programs:
Increment Binary
3-State Busy Beaver
Palindrome Check
Unary Addition
Transition Table (current state highlighted)
State
Read
Write
Move
Next State
Tape Input
Load Tape
Execution Log
About Turing Machines
A Turing machine has: an infinite tape of symbols, a read/write head, a finite set of states, and a transition function.
Church-Turing thesis:
Any effectively computable function can be computed by a Turing machine.
Busy beaver:
The n-state BB(n) is the maximum number of 1s that an n-state halting TM writes on a blank tape. BB(5) = 4098. BB(6) is unknown!