Turing Machines: short notes (Theory of Computation)

Revision mode

Introduction

A Turing machine (TM) is a finite-state controller with a doubly infinite (or one-way infinite) tape and a read/write head. It is the standard model of general-purpose computation. Languages recognized by TMs are the recursively enumerable (r.e.) languages; languages decided by TMs that always halt are the recursive (decidable) languages. The working core is the definitions, simple TM designs, variants (multitape, nondeterministic) and the Church-Turing thesis at statement level.

Prerequisites

Pushdown Automata: limited auxiliary memory (stack) versus unrestricted tape.

Core concepts

Formal definition

A TM is $M = (Q, \Sigma, \Gamma, \delta, q_0, q_{\mathrm{accept}}, q_{\mathrm{reject}})$ with tape alphabet $\Gamma$ containing the blank $\sqcup$ , input alphabet $\Sigma \subset \Gamma \setminus \{\sqcup\}$ , and

\delta: (Q \setminus \{q_{\mathrm{accept}}, q_{\mathrm{reject}}\}) \times \Gamma \to Q \times \Gamma \times \{L,R\}.

A step reads the tape cell under the head, writes a symbol, moves one cell left or right, and updates the state. Computation accepts by entering $q_{\mathrm{accept}}$ and rejects by entering $q_{\mathrm{reject}}$ .

Configurations

A configuration $u q v$ means tape contents $uv$ (infinite blanks beyond), state $q$ , head on the first symbol of $v$ . One step: if $\delta(q, b) = (p, c, R)$ then $u\,q\,bv \vdash u c\,p\,v$ ; if $\delta(q, b) = (p, c, L)$ then $ua\,q\,bv \vdash u\,p\,ac\,v$ . On a one-way infinite tape a left move in the leftmost cell leaves the head where it is (Sipser's convention).

Three outcomes

On input $w$ a TM accepts (reaches $q_{\mathrm{accept}}$ ), rejects (reaches $q_{\mathrm{reject}}$ , or in HMU's convention halts with no move defined), or loops (runs forever). Looping is not rejection: an observer can never be sure that a long run will not still accept.

Recognizers versus deciders

Recognizer. Accepts every string in $L$ , and either rejects or loops on strings not in $L$ . $L$ is r.e.
Decider. Always halts; accepts iff the string is in $L$ . $L$ is recursive (decidable).

Every decidable language is r.e.; the converse is false (for example $A_{\mathrm{TM}}$ is r.e. but undecidable).

Variants

Multitape TMs, nondeterministic TMs, and TMs with stay-option heads all recognize the same class of languages as single-tape deterministic TMs (Sipser 3.2; HMU 8.4). Time bounds change; language power does not.

Model	Power	Cost of simulation by a 1-tape DTM
$k$ -tape TM	= TM	$t(n)$ steps become $O(t(n)^2)$
Nondeterministic TM	= TM (both for recognizing and for deciding)	$t(n)$ steps become $2^{O(t(n))}$ (breadth-first search of the computation tree)
Stay option, two-way infinite or semi-infinite tape, multiple heads, 2-D tape	= TM	polynomial
Two-stack PDA; queue automaton; 2-counter machine	= TM	two stacks hold the tape left and right of the head
PDA (one stack); 1-counter machine	CFL or smaller	not universal
Linear bounded automaton (tape limited to the input)	CSL	the membership problem is decidable
TM that never writes, or that only moves right	regular	a read-only two-way head adds no power (2DFA = DFA)
Enumerator (prints strings, possibly forever)	RE	prints $L$ iff a TM recognizes $L$

A language is decidable iff some enumerator prints it in string order (shortlex). A finite automaton with a stack is not a TM; with two stacks it is.

How it works

High-level design macros

TMs are described at a high level in exams: "scan right to the first $a$ , cross it off, scan right to the first $b$ ," and so on. Storage in the finite state holds a constant amount of data; the tape holds unbounded data.

Example: recognize $a^n b^n c^n$

Repeatedly cross off one $a$ , one $b$ , one $c$ from left to right; accept when nothing but crossed symbols remain; reject on mismatch. Example 1 gives the full transition table and a trace.

Turing machine tape configuration and a transition step — Figure 1. TM configuration with tape cells, head on one cell, and current state; one transition shows write and move for the a^n b^n c^n crossing-off machine.

In Figure 1 the state labels $q_{\mathrm{scan}}$ and $q_b$ are $q_0$ and $q_1$ of the table in Example 1: the step drawn is $\delta(q_0, a) = (q_1, X, R)$ .

Algorithms and pseudocode

Text

TM-STEP(M, config)
1  read symbol under head
2  apply delta to get (new_state, write, dir)
3  write symbol; move head; set state
4  if state is accept or reject: halt

Practice both a high-level TM description and step-by-step transition traces.

Mathematical explanation

Church-Turing thesis

Every effectively computable function is computable by a Turing machine. It is a thesis, not a theorem: it identifies the informal notion of algorithm with TM computability. All standard programming languages are TM-equivalent in power.

Encoding machines

Finite descriptions of TMs can be encoded as strings (or integers). That encoding enables universal machines and undecidability proofs in Decidability and Undecidability.

Worked examples

Example 1: $\{a^n b^n c^n\}$

Tape alphabet $\{a, b, c, X, Y, Z, \sqcup\}$ ; $a$ becomes $X$ , $b$ becomes $Y$ , $c$ becomes $Z$ . Any pair not listed goes to $q_{\mathrm{reject}}$ .

State	Reads	Write, move, next	Meaning
$q_0$	$a$	$X, R, q_1$	cross the leftmost $a$
$q_0$	$Y$	$Y, R, q_4$	no $a$ left: check the rest
$q_0$	$\sqcup$	accept	empty input ( $n = 0$ )
$q_1$	$a, Y$	same, $R, q_1$	skip to the first $b$
$q_1$	$b$	$Y, R, q_2$	cross it
$q_2$	$b, Z$	same, $R, q_2$	skip to the first $c$
$q_2$	$c$	$Z, L, q_3$	cross it, turn back
$q_3$	$a, b, Y, Z$	same, $L, q_3$	return left
$q_3$	$X$	$X, R, q_0$	next round
$q_4$	$Y$	$Y, R, q_4$	only $Y$ 's, then $Z$ 's
$q_4$	$Z$	$Z, R, q_5$
$q_5$	$Z$	$Z, R, q_5$
$q_5$	$\sqcup$	accept	all counts matched

Trace on aabbcc (first round): $q_0\,aabbcc \vdash X q_1\,abbcc \vdash Xa\,q_1\,bbcc \vdash XaY q_2\,bcc \vdash XaYb\,q_2\,cc \vdash XaY q_3\,bZc \vdash Xa\,q_3\,YbZc \vdash X q_3\,aYbZc \vdash q_3\,XaYbZc \vdash X q_0\,aYbZc$ . The whole run accepts after 23 steps. On $a^n b^n c^n$ the machine takes exactly $4n^2 + 3n + 1$ steps, so it runs in $O(n^2)$ time on inputs of length $3n$ ; it halts on every input, so it is a decider. It rejects abcc (in $q_5$ it reads $c$ ) and aabbc (in $q_2$ it reaches $\sqcup$ looking for a second $c$ ).

Example 2: $\{ ww \mid w \in \{0,1\}^* \}$

Find the middle (mark off matching ends, or use multitape copy); compare halves. Decidable.

Example 3: multitape simulation

A $k$ -tape TM simulates on one tape by interleaving tracks; the language is unchanged.

Example 4: nondeterministic TM

Guess a witness (for example a satisfying assignment) and verify deterministically. Nondeterministic TMs recognize and decide exactly the same languages as deterministic ones (Sipser 3.2); only the time can grow exponentially. An NTM decider must halt on every branch.

Example 5: loops

A TM whose only move is "on any symbol, move right" never halts, so it recognizes $\emptyset$ but is not a decider. The language $\emptyset$ is still decidable, by a different TM that rejects at once. Decidability is a property of the language (some TM decides it), not of one machine.

Example 6: closure, and "L and its complement both RE"

Decidable languages are closed under union, intersection, complement, concatenation and star. RE languages are closed under union, intersection, concatenation and star, but not complement.
For union of two recognizers, run them alternately one step at a time (dovetailing); running $M_1$ to completion first fails when $M_1$ loops.
Theorem. If $L$ and $\overline{L}$ are both RE, then $L$ is decidable: run both recognizers in parallel; exactly one accepts, and it must halt. Hence $\overline{A_{\mathrm{TM}}}$ is not RE.
Four groups. Call $L$ co-RE when $\overline{L}$ is RE. The theorem says RE and co-RE together give exactly the decidable languages, so every language falls in exactly one of four groups.

Group	Example	Argument
decidable (recursive)	$A_{\mathrm{DFA}} = \{\langle D, w \rangle \mid D \text{ a DFA accepting } w\}$	a TM runs $D$ on $w$ for $\lvert w \rvert$ steps and always halts
RE but not co-RE	$A_{\mathrm{TM}}$ , $HALT_{\mathrm{TM}}$	the universal TM recognizes $A_{\mathrm{TM}}$ , which is undecidable by diagonalization; $HALT_{\mathrm{TM}}$ is recognized by simulation and is undecidable because $A_{\mathrm{TM}} \le_m HALT_{\mathrm{TM}}$ ; an undecidable RE language is not co-RE, by the theorem
co-RE but not RE	$\overline{A_{\mathrm{TM}}}$ , $E_{\mathrm{TM}} = \{\langle M \rangle \mid L(M) = \emptyset\}$	$\overline{A_{\mathrm{TM}}}$ is the complement of an RE language and is not RE, by the theorem; $\overline{E_{\mathrm{TM}}}$ is RE (dovetail $M$ over all strings and accept when one is accepted), and $\overline{A_{\mathrm{TM}}} \le_m E_{\mathrm{TM}}$ , so $E_{\mathrm{TM}}$ is not RE
neither RE nor co-RE	$EQ_{\mathrm{TM}} = \{\langle M_1, M_2 \rangle \mid L(M_1) = L(M_2)\}$	$\overline{A_{\mathrm{TM}}} \le_m EQ_{\mathrm{TM}}$ , so it is not RE; $A_{\mathrm{TM}} \le_m EQ_{\mathrm{TM}}$ , so $\overline{A_{\mathrm{TM}}} \le_m \overline{EQ_{\mathrm{TM}}}$ and it is not co-RE

The reductions. For a pair $\langle M, w \rangle$ let $M_w$ be the TM that ignores its own input, runs $M$ on $w$ and accepts if $M$ accepts. Then $L(M_w) = \Sigma^*$ if $M$ accepts $w$ , and $L(M_w) = \emptyset$ otherwise. Let $M_\emptyset$ reject everything and $M_{\mathrm{all}}$ accept everything.
- $\langle M, w \rangle \mapsto \langle M_w \rangle$ maps $\overline{A_{\mathrm{TM}}}$ to $E_{\mathrm{TM}}$ .
- $\langle M, w \rangle \mapsto \langle M_\emptyset, M_w \rangle$ maps $\overline{A_{\mathrm{TM}}}$ to $EQ_{\mathrm{TM}}$ .
- $\langle M, w \rangle \mapsto \langle M_{\mathrm{all}}, M_w \rangle$ maps $A_{\mathrm{TM}}$ to $EQ_{\mathrm{TM}}$ .
"Not RE" alone does not place a language: $E_{\mathrm{TM}}$ is not RE but is co-RE, while $EQ_{\mathrm{TM}}$ is neither.

Example 7: counting argument

TMs have finite descriptions, so there are countably many. The set of languages over $\{0,1\}$ is the power set of a countable set, which is uncountable (diagonalization). Therefore most languages are not RE. The diagonal language $\{\langle M \rangle \mid M \text{ does not accept } \langle M \rangle\}$ is an explicit example.

Important properties and observations

Tape is unbounded but only finitely many non-blank cells appear at any finite time.
Acceptance needs only reach $q_{\mathrm{accept}}$ ; the tape contents at accept can be anything.
PDA $\subsetneq$ TM in power ( $\{a^n b^n c^n\}$ separates them).
Universal TM: a TM $U$ with $L(U) = \{ \langle M,w \rangle \mid M \text{ accepts } w \}$ .

Common misconceptions.

"TMs always halt." Only deciders do.
"Nondeterministic TMs recognize more languages." They do not.
"Infinite tape means infinite time is allowed for a decision." Decisions must halt in finite time.
"A TM with a two-way read-only tape is more powerful than a DFA." It accepts only regular languages.
"A two-stack PDA is just a PDA." Two stacks simulate a tape, so it is as powerful as a TM.
"Rejecting and looping are the same." For a recognizer they both mean "not in $L$ ", but only a halting reject can be observed.

GATE examination perspective

RECOGNIZE VS DECIDE. Keep the words apart: a recognizer may loop on strings outside $L$ ; a decider halts on every input.
HIGH-LEVEL DESCRIPTIONS. Write clear phases; do not invent 50-state tables unless asked.
VARIANTS PRESERVE LANGUAGES. Quote the equivalence.
SEPARATION EXAMPLES. $a^n b^n c^n$ not CFL but decidable.
MODEL POWER TABLE. Two stacks, a queue, or two counters equal a TM; one stack does not; read-only TMs are finite automata.
COMPLEMENT RULE. $L$ RE and $\overline{L}$ RE implies decidable; so if $L$ is RE but not decidable, $\overline{L}$ is not RE.
FOUR GROUPS. Decidable; RE not co-RE ( $A_{\mathrm{TM}}$ ); co-RE not RE ( $\overline{A_{\mathrm{TM}}}$ , $E_{\mathrm{TM}}$ ); neither ( $EQ_{\mathrm{TM}}$ ). Place a language by checking both $L$ and $\overline{L}$ .
STEP COUNTING. Crossing-off machines take quadratic time on one tape; a second tape makes $\{a^n b^n c^n\}$ linear.

Summary

Sources

M. Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage Learning: Section 3.1 (Turing machines), Section 3.2 (variants: multitape, nondeterministic, enumerators), Section 3.3 (the definition of algorithm), Section 4.2 (undecidability; the diagonalization method).
J. E. Hopcroft, R. Motwani, J. D. Ullman, Introduction to Automata Theory, Languages, and Computation, 3rd ed., Pearson Addison-Wesley, Section 8.2 (the Turing machine), Section 8.3 (programming techniques for TMs), Section 8.4 (extensions to the basic TM), Section 8.5 (restricted TMs: semi-infinite tapes, multistack machines, counter machines).
P. Linz, An Introduction to Formal Languages and Automata, 6th ed., Jones & Bartlett Learning, Section 9.1 (the standard Turing machine), Section 10.1 to 10.5 (other models: variations, multitape, nondeterministic, universal TM, linear bounded automata), Section 11.1 (recursive and recursively enumerable languages).