Turing machines

TM simulator · Chapter 3.1

Simulate Turing machines step by step

A Turing machine reads and writes on an infinite tape and moves its head left or right (Sipser, Chapter 3.1). Draw one with Sipser's labels, watch it run on the tape one step at a time, read its configurations, and see its formal definition.

Writing transition labels

TypeMeans
0->x,R or 0→x,Rread 0, write x, move right
x→Rread x, leave it, move right
0,1,x→Lthe same move for each symbol listed
␣ (or \blank)the blank symbol
L, R, Smove left, move right, stay put (S is a variant, not in Sipser's definition)
0→R; 1→Ltwo rules on one arrow, drawn on two lines

How the machine runs

  1. The input is written on the tape from the first cell, the rest is blank, and the head starts on the first cell.
  2. The machine accepts when it enters q_accept (a state with “accept” in its name, or drawn with a double circle) and rejects when it enters q_reject.
  3. As in Sipser's diagrams, a missing transition means the machine goes to q_reject. Moving left from the first cell leaves the head where it is.
  4. A machine may run forever. The page stops after the step limit you choose and says so, instead of guessing.

Configurations

  1. A configuration u q v means the tape holds uv, the state is q and the head is on the first symbol of v (Sipser, Section 3.1).
  2. The Configurations list shows every step of a run, like Sipser's trace for Example 3.7.
  3. For a nondeterministic machine, the page explores every branch and shows an accepting one.