Skip to content
Tutorials Center
My learning

Topics

Lesson 32 of 59 Β· Turing Machines

Turing Machines: Definition and First Examples

Learn what a Turing machine is: tape, head, states and transitions. Build and trace a machine for 0^n 1^n and a binary incrementer with a Python simulator.

A Turing machine (TM) is the simplest model that captures everything we mean by "computing". It was introduced by Alan Turing in 1936. Picture a finite control (like a DFA) attached to an infinite tape divided into cells. A head points at one cell. In each step the machine reads the cell, writes a new symbol, moves the head one cell left or right, and changes state. That is all, yet any algorithm you can write in any programming language can be carried out by such a machine.

Compared with the pushdown automaton, a Turing machine has three powers: it can write on its input, it can move in both directions, and its tape is unbounded in memory. Together these make it strictly stronger than every machine in the earlier chapters.

The parts of a Turing machine

Tape Infinite row of cells, blank by default.
Head Reads and writes one cell at a time.
States Finite control with start, accept, reject.
1 / 2

Formal definition

A Turing machine is a 7-tuple (Q, Ξ£, Ξ“, Ξ΄, q0, q_accept, q_reject):

  • Q: finite set of states, with q0 the start state and the distinct halting states q_accept and q_reject.
  • Ξ£: the input alphabet, which never contains the blank symbol _.
  • Ξ“: the tape alphabet, with Ξ£ βŠ‚ Ξ“ and _ ∈ Ξ“. It also holds helper symbols such as X or Y for marking.
  • Ξ΄: (Q \ {halting}) Γ— Ξ“ β†’ Q Γ— Ξ“ Γ— {L, R}: the transition function.

The input is written at the left end of the tape; every other cell holds _. A transition Ξ΄(q, a) = (p, b, R) reads: "in state q on symbol a, write b, move right, enter state p." Our simulator also allows S (stay), which does not add power.

A configuration records everything: the tape content, head position and state. It is often written u q v, meaning the tape holds uv, the state is q and the head sits on the first symbol of v. A machine has three possible fates on an input: it accepts, it rejects, or it loops forever. The third outcome has no counterpart in DFAs or PDAs and is the source of undecidability later.

If the machine has no transition for a state and symbol, our simulator treats it as an implicit rejection. Textbooks often say the same: "missing transitions go to q_reject".

A simulator you can reuse

This is the engine for the whole chapter. Rules are written as text, one per line: state,symbol -> new_state,written_symbol,move. The function returns three values: whether the machine accepted, the final non-blank tape content, and the number of steps. With trace=N it prints the first N configurations, with the head position in brackets.

A machine for 0^n 1^n

The idea is to cross off one 0 and one matching 1 per round:

  1. q0: find the leftmost unmarked 0, replace it with X.
  2. q1: move right (skipping 0s and Ys) to the first 1, replace it with Y.
  3. q2: move left back to the X, then step right and repeat from q0.
  4. If q0 sees a Y instead of a 0, every 0 was matched: q3 checks that only Ys remain, then accepts at the first blank.
flowchart LR
    q0(["q0"]) -->|"0 β†’ X, R"| q1(("q1"))
    q1 -->|"0,Y β†’ same, R"| q1
    q1 -->|"1 β†’ Y, L"| q2(("q2"))
    q2 -->|"0,Y β†’ same, L"| q2
    q2 -->|"X β†’ X, R"| q0
    q0 -->|"Y β†’ Y, R"| q3(("q3"))
    q3 -->|"Y β†’ Y, R"| q3
    q3 -->|"_ β†’ _, R"| qa((("qa")))
    q0 -->|"_ β†’ _, R"| qa

Edge labels read: symbol seen β†’ symbol written, head move. A missing edge means reject.

Python Trace the machine for 0^n 1^n

Press Run (or Ctrl + Enter) to see the result here.

Program input Β· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In the trace, Xs grow from the left, Ys from the middle, and the head sweeps back and forth between them. Each full round costs about n steps, so the whole run takes about nΒ² steps, a typical price for a single-tape machine.

Testing against the definition

Always test a machine exhaustively on short strings, as we did for PDAs. The loop below compares the machine with the truth on all binary strings up to length 9, and also times how the step count grows.

Python Check the machine on every short string

Press Run (or Ctrl + Enter) to see the result here.

Program input Β· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The step counts grow roughly four times when n doubles, the signature of quadratic time.

Turing machines compute functions too

A TM is not only a yes/no recognizer. When it halts, the tape can hold an output. Here is a classic example: add 1 to a binary number. Move to the right end, then walk left turning 1s into 0s until you find a 0 (or a blank) and turn it into 1, just like a carry.

Python Binary increment

Press Run (or Ctrl + Enter) to see the result here.

Program input Β· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

When the machine halts in qa, the tape content is the answer. For a decider only the accept/reject verdict matters; for a function machine the tape is the result. Unary arithmetic machines take this idea much further.

Languages and kinds of machines

  • A language is Turing-recognizable (recursively enumerable) if some TM accepts exactly its strings. On strings outside the language the machine may reject or loop.
  • A language is Turing-decidable (recursive) if some TM halts on every input, accepting members and rejecting non-members.

We study these two classes in recursive and recursively enumerable languages.

Check your understanding

Quick check Β· 4 questions

of 4 answered You scored / 4 Β· perfect!

  1. 1. What can a Turing machine do that a pushdown automaton cannot?

    A TM can rewrite cells and move in both directions along an infinite tape; a PDA only accesses the top of a stack.
  2. 2. What are the three possible outcomes of a Turing machine run on an input?

    Unlike a DFA, a TM may never halt; this third outcome is the root of undecidability.
  3. 3. In the 0^n 1^n machine, why does q2 move left?

    After marking a matching 1, the head returns to X so q0 can find the next unmarked 0.
  4. 4. Roughly how many steps does the single-tape 0^n 1^n machine need?

    Each of the n rounds sweeps across about n cells.

Summary

  • A Turing machine has a finite control, an infinite tape and a read/write head that moves left or right.
  • A transition reads a symbol, writes one, moves, and changes state; halting states are accept and reject.
  • A run can accept, reject or loop forever.
  • Marking symbols (X, Y) let the machine remember progress on the tape.
  • TMs can compute functions as well: the final tape is the output.

Next: Variants of Turing machines and the Church–Turing thesis