Run the machine to see it in action. At any time, you can step or pause to get a closer look, or reset to start over.
There are over a dozen different example machines to explore.
Most of the examples take input. Experiment with different inputs to see what happens! Edit the code and click Load machine to sync your changes.
The colored circles are states. The squares underneath are tape cells.
The current state and tape cell are highlighted.
At each step, a Turing machine reads its current state and tape symbol, and looks them up in its transition table for an instruction. Each instruction does 3 things:
That’s it!
This repeats step after step, until the machine reaches a combination of state and symbol that don’t have an instruction defined. At that point it halts.
A Turing machine is an abstract device to model computation as rote symbol manipulation.
Each machine has a finite number of states, and a finite number of possible symbols. These are fixed before the machine starts, and do not change as the machine runs.
There are an infinite number of tape cells, however, extending endlessly to the left and right. Each tape cell bears a symbol. Any cell not part of the input or not yet written to bears the blank symbol by default. Notice that at any step, only finitely many cells bear a non-blank symbol.
(As a mathematical model, a Turing machine has infinite memory (an infinite tape) so as to not artificially restrict its power. In practice, many machines of interest take finite memory, and can be fully simulated for manageable input sizes. Even machines that use infinite memory—and hence never halt—use at most one new tape cell per step, and so can be simulated to an extent.)
The formal definition of a Turing machine has slight variations but essentially is a tuple (ordered list) comprising
where Q, Σ, and Γ are finite nonempty sets. Some definitions also require that the blank symbol not be part of the input (b ∉ Σ).
As an example, a formal description for the “binary increment” machine is as follows:
Q = { right, carry, done }
q₀ = right
Σ = { 1, 0 }
Γ = { 1, 0, ' ' }
b = ' '
δ(right, 1) = (1, R, right)
δ(right, 0) = (0, R, right)
δ(right, ' ') = (' ', L, carry)
δ(carry, 1) = (0, L, carry)
δ(carry, 0) = (1, L, done)
δ(carry, ' ') = (1, L, done)
Note that for simplicity, the simulator limits each symbol to one character. Furthermore, input is not checked for conformance with an input alphabet, in exchange for not having to define input and tape alphabets.
(The behavior of a Turing machine can also be described in mathematical terms if desired. Without going into too much detail, this involves defining how a configuration of a machine—its state, tape contents, and tape head position (current cell)—leads to the next configuration, based on the transition function. To start with, the tape’s contents may be defined as a function from integers to symbols, with the head position as an integer, and each move {L, R} adding -1 or +1 respectively to the head position.)
Some aspects of the definition vary from author to author, but the differences come down to preference and do not affect computational power. That is, machines on one model can be simulated or converted to run on another model.
Some of the variations you may come across:
The simulator was designed with these and other considerations in mind.
For a very readable introduction to Turing machines, including their significance and interesting implications, see the excellent entry in the Stanford Encyclopedia of Philosophy.
Make spinoffs from the examples or your own creations by using Edit > Duplicate document. You can also start from scratch with a new blank document.
All it takes to describe a Turing machine is a start state, blank symbol, and transition table.
# Adds 1 to a binary number. input: '1011' blank: ' ' start state: right table: # scan to the rightmost digit right: 1: R 0: R ' ': {L: carry} # then carry the 1 carry: 1: {write: 0, L} 0: {write: 1, L: done} ' ': {write: 1, L: done} done:
Here the states are right
, carry
, and done
.
The symbols are '1
', '0
', and '
'.
We designate one state the start state, and one symbol the blank symbol (found on unmarked tape cells).
A state and a symbol together map to an instruction.
In the carry
state, for instance, the symbol 1
maps to the instruction {write: 0, L}
.
When no instruction is defined, as in the done
state, the machine halts.
{write: symbol, move: state}
{write: 1, L: done}
writes the symbol 1
,
moves the tape head left (L
), and goes to the done
state.
For brevity, you can omit the symbol and state if they stay the same.
{L: carry}
writes the same symbol that was read,
moves the tape head left, and goes to the carry
state.R
(shorthand for {R}) simply moves the tape head right.
It writes back the same symbol and stays in the same state.The code is written in YAML 1.2, a general-purpose data format.
If you’re familiar with JSON, YAML is similar, but designed to be more readable.
Mappings can use indent instead of brackets {}
, and strings can often be included directly without quotes.
Some strings need to be quoted: for example, those that start/end with a space, or include certain characters that have special meaning in YAML. If a string is causing problems, try putting quotes around it.