State
Steps
Symbols on the tape
Status

In state Reads Writes Moves Next state

More about Turing machines

Turing machine simulator

A Turing machine is the simplest possible computer: a head that reads one symbol of an endless tape, writes a symbol, moves one cell left or right and changes its state, following a short table of rules. Alan Turing invented it in 1936, and everything your computer does can in principle be done this way. Write your own rules or load an example, press Run, and watch the tape change step by step, with a diagram of its whole history underneath. Choose a program or write your own, enter the input and press Run, or Step to follow one rule at a time; Back undoes a step. Each line of the program is one rule: state, symbol read, symbol to write, move (L, R or N for no move) and the next state, for example A 0 -> 1 R B. Use _ for a blank cell. The machine starts in the state of the first rule, on the first symbol of the input, and stops in H, accept or reject, or when no rule fits. The diagram shows the tape after every step, from top to bottom.

How it works

  1. Choose an example program or write rules like A 0 -> 1 R B, one per line, and type the input.
  2. Press Run to watch the head move, or Step to follow one rule at a time; Back undoes a step.
  3. Read the state, the steps and the symbols on the tape in the tiles, and the tape's history in the diagram.

How the machine works

At every moment the machine is in one of a few states and its head sits on one cell of the tape. The rule for that state and the symbol under the head says three things: which symbol to write in the cell, whether to move left, right or not at all, and which state to go to next. That is the whole machine. It stops when it reaches a halting state, such as H, accept or reject, or when no rule fits. A program to add 1 to a binary number needs only nine such rules.

Busy beavers

Which machine with n states, started on a blank tape, writes the most 1s before it halts? Tibor Radó asked this in 1962. The champions are called busy beavers, and they grow faster than any function a computer can calculate. Two states give 4 ones in 6 steps, three states 6 ones, four states 13 ones in 107 steps. The five-state champion, found in 1989, writes 4,098 ones in 47,176,870 steps, and in 2024 an online collaboration proved with computer-checked mathematics that no other five-state machine that halts runs longer.

Frequently asked questions

How do I write a rule?

One rule per line: the current state, the symbol it reads, the symbol to write, the move (L, R or N) and the next state, for example A 0 -> 1 R B. The arrow and commas are optional. Use _ for a blank cell and # for a comment. The machine starts in the state of the first rule; a next state called H or halt stops it, and accept and reject stop it with a verdict.

Can a Turing machine really compute anything?

Anything that any computer can compute, given enough tape and time: that is the Church–Turing thesis. A Turing machine has no memory limit, so in that sense it is more powerful than any real computer, though far slower. What it cannot do is answer every question: Turing proved that no machine can decide, for every program and input, whether it will halt.

Why does the counter never stop?

Its rules never lead to a halting state. It keeps adding 1 to a binary number at the right end of the tape and walking back, so the number grows forever. Turing's halting problem says that no general method can tell, for every machine, whether it will halt; for this simple counter you can see it, but for some machines with only six states nobody knows yet.

How can the five-state busy beaver run 47 million steps here?

The tape is stored as a compact array that grows in both directions, and in the fastest setting the app runs hundreds of thousands of steps between screen updates, so the whole run takes a few seconds in a modern browser. The diagram records only the first 400 steps, since a picture of 47 million rows would not fit on any screen.

Is anything sent to a server?

No. The program runs in your browser, and your program and input stay in this browser's local storage.

Ready to try it?

Open PictorX in your browser — no install, no credit card required to start.

Go to Editor