ToolSphere

Turing Machine Simulator

Computer science

Run a Turing machine step by step: write the rules and watch the head move along the tape. Examples for aⁿbⁿ, binary +1 and palindromes.

Turing machine simulator

Pick an example or type an input: the result shows at once. Edit the rules below, then step through the tape.

Accepted after 13 steps. Reached accept state qa. Tape: XXYY

Directives: accept: qa, reject: qr, start: q0 (defaults to the first rule's state). Lines starting // are comments.

Step 0 of 13 · state q0

▼␣
▼␣
▼␣
▼␣
▼␣
▼␣
▼␣
▼␣
▼␣
▼␣
▼a
▼a
▼b
▼b
▼␣
▼␣
▼␣
▼␣
▼␣
▼␣
▼␣

Next: in q0 reading a, write X, move right, go to q1.

Every step

#StateTape (head in [ ])Rule applied
0q0[a]abbq0, a → q1, X, R
1q1X[a]bbq1, a → q1, a, R
2q1Xa[b]bq1, b → q2, Y, L
3q2X[a]Ybq2, a → q2, a, L
4q2[X]aYbq2, X → q0, X, R
5q0X[a]Ybq0, a → q1, X, R
6q1XX[Y]bq1, Y → q1, Y, R
7q1XXY[b]q1, b → q2, Y, L
8q2XX[Y]Yq2, Y → q2, Y, L
9q2X[X]YYq2, X → q0, X, R
10q0XX[Y]Yq0, Y → q3, Y, R
11q3XXY[Y]q3, Y → q3, Y, R
12q3XXYY[_]q3, _ → qa, _, S
13qaXXYY[_]halt

On this browser only

Give feedback

Did this tool help?

Tell us what worked, what didn’t, or what you’d like next.

Opens Google Forms in a new tab with this tool’s name filled in. No sign-in or email required. Feedback is optional.

Coming from JFLAP? See what carries over and what JFLAP still does better →

How to use Turing Machine Simulator

  1. 1Write one rule per line as state, read -> state, write, move , where move is L, R or S (stay). Use _ for a blank cell.
  2. 2Add accept: qa (and optionally reject: qr ). The start state is the first rule's state unless you write start: q0 .
  3. 3Type an input, or load an example: aⁿbⁿ, binary increment or palindromes.
  4. 4Step through with the arrows or press play to watch the head; click any row of the step table to jump there.

About Turing Machine Simulator

The simplest computer

A Turing machine is a head on an infinite tape of cells. At each step it reads the symbol under the head, and depending on its current state and that symbol, it writes a symbol, moves one cell left or right, and switches state. That is all, and yet it can compute anything any computer can: the Church–Turing thesis says this model captures exactly what "computable" means. Writing small machines by hand is how theory-of-computation courses make that concrete.

Reading the rules

The rule q1, b -> q2, Y, L means: in state q1 reading b, write Y, move left, and go to q2. The machine halts when it enters an accept or reject state, or when no rule matches the current state and symbol, which counts as rejecting. The tape starts with the input written from the head rightwards; every other cell is blank.

The examples

aⁿbⁿ shows the standard marking technique: replace the first a with X, run right to the first b and replace it with Y, run back, and repeat. If every a finds a b and nothing is left over, accept. Binary +1 walks to the end of the number and carries leftwards, turning trailing 1s into 0s until it can write a 1. Palindrome erases the first symbol, runs to the end to check the last one matches, erases that too, and repeats from both ends inwards.

Halting and looping

Unlike finite automata, a Turing machine might never stop. The simulator runs up to 5,000 steps and reports "did not halt" beyond that. No program can decide in general whether a machine halts (the halting problem), so a step limit is the honest answer. Machines here are deterministic: one rule at most for each state and symbol.

Where this fits

Turing machines sit at the top of the hierarchy. Below them, the PDA simulator covers context-free languages with a single stack, and the NFA & DFA simulator covers regular languages with no memory beyond the current state. Comparing what each machine can do with the same language is the quickest way to see why the hierarchy has the levels it has.

Guides and tutorials

Frequently asked questions

How do I write a Turing machine rule?

Write state, read -> new state, write, move on its own line, for example q0, a -> q1, X, R . The move is L (left), R (right) or S (stay). Use _ for the blank symbol.

When does the machine halt?

When it enters a state listed after accept: or reject:, or when there is no rule for the current state and symbol, which counts as a rejection. Machines that keep running are stopped after 5,000 steps and reported as not halting.

Does it support nondeterministic or multi-tape Turing machines?

No: it simulates the standard deterministic single-tape machine, so each state and symbol may have at most one rule. Every nondeterministic or multi-tape machine has an equivalent single-tape deterministic one.

What is the difference between a Turing machine and a PDA?

A pushdown automaton can only use a stack, reading the input once from left to right. A Turing machine can move both ways on its tape and overwrite it, which makes it strictly more powerful: it recognises languages like aⁿbⁿcⁿ that no PDA can.

Have a suggestion for Turing Machine Simulator?Share your feedback ↗