Turing Machines

The model

A Turing machine is a tuple $(Q, \Gamma, \delta, q_0, F)$: a finite set of states, a tape alphabet, a transition function

an initial state, and accepting states. Despite its austerity, the model captures — by the Church–Turing thesis — everything we mean by effective computation.

Undecidability

The halting problem asks: given a machine $M$ and input $w$, does $M$ halt on $w$? Turing’s diagonal argument shows no machine decides this. Suppose $H$ decided halting; build $D$ that, on input $\langle M \rangle$, runs $H(M, \langle M \rangle)$ and does the opposite. Then

a contradiction. Rice’s theorem generalises: every non-trivial semantic property of programs is undecidable.

An interactive machine

The machine below computes binary increment: state scan walks right to the end of the input, then carry flips trailing 1s to 0s until it can write the carried 1. Try 111 to watch a full carry chain.

The cost model here (one cell, one step) is what makes statements like those in Asymptotic Notation meaningful.