Try it out

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.

What’s going on?

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:

  1. write a symbol to the current tape cell
  2. move to the left or right by one cell
  3. set the new state

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

  • states Q
  • start state q₀ ∈ Q
  • input alphabet Σ
  • tape alphabet Γ, where Σ ⊆ Γ
  • blank symbol b ∈ Γ
  • transition function δ that has the type Q × Γ → Γ × {L, R} × Q

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:

  1. The tape only extends infinitely to the right. The left end is where the tape head (current cell) begins. Moving left at the left end keeps the tape head on the same cell.
  2. In addition to “move left” (L) or “move right” (R), a tape head movement can be “no move” (N).
  3. Instead of moving the tape head, a movement shifts the tape itself, so that the directions of L & R are swapped. (Shifting the tape left is the same as moving the head right.)
  4. The machine can only halt in one of two states: a state designated the accept state, or another state designated the reject state. These states have no exiting transitions. All the other states must have transitions defined for every symbol.

The simulator was designed with these and other considerations in mind.

  1. Limiting the tape was inconvenient, often requiring marking the left end with a symbol, and writing numbers in reverse. On the other hand, machines created for a right-infinite tape can run on a doubly-infinite tape with little to no modification.
  2. Compared to L and R, “no move” (N) seems to be seldom used. For now it has been omitted for conceptual simplicity.
  3. It's more intuitive to set the current cell directly by moving the tape head. Turing also follows this convention. (The visualization however stays centered on the head to avoid issues of the head moving out of view.)
  4. The accept/reject convention still works; it's just not required. In fact the simulator supports a convenient shorthand, demonstrated in some of the examples: omit the reject state and all transitions to it, and treat halting on a non-accept state as an implicit rejecting transition. This reduces tedious boilerplate code and makes for a cleaner diagram.

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 your own

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.

Example

# 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.

Instruction format

The general form of an instruction has three parts: 
{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.

Tips

Editor keyboard shortcuts

More keyboard shortcuts are available on the full list.

Misc. tips

  • Drag or click a state node to fix it in place; double-click to release it.
  • Don’t hesitate to duplicate. Use Edit > Duplicate document to create a snapshot of your current document whenever you’re about to make a larger edit.
  • Changes are autosaved to your browser’s local storage. They will stay there between sessions, but be careful when clearing browser data. You can create backups by downloading your documents.
  • Incognito / Private Browsing mode uses a separate temporary storage. This is useful for importing or editing documents that you want to try but don’t want to keep.

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.