Theory of Computation: Lecture 4

From Finite Memory to Work Tape

Finite automata have fixed memory: no matter how long the input is, the machine remembers only one of finitely many states. That is why languages such as

$$C=\{w\in\{0,1\}^*\mid w\text{ has as many }0\text{s as }1\text{s}\}$$

are not regular. The problem itself is easy for an ordinary algorithm: count the symbols, or pair them off. What finite automata lack is memory whose used portion can grow with the input.

Tape. A row of cells used as memory. Each cell stores one symbol. A head points to one cell at a time and can read or overwrite that cell. The input starts in the leftmost cells; the rest of the tape is blank.

Unbounded work memory. Memory with no fixed finite bound on how many tape cells may be used during a computation. Each input still uses only finitely many cells at any finite time, but longer inputs may require more cells.

A finite automaton has a fixed notebook with one page. A Turing machine has a finite program and as much blank paper as the computation needs.

Single-tape encoding. Storing the input, work memory, and output on one tape. Different regions of the tape can be separated by delimiters such as #. Several tapes may be easier to draw, but one tape is enough to represent the same computation.

Turing Machines

Turing machine (TM). A finite-state control attached to an infinite tape. At each step, the machine reads the symbol under its head, writes one tape symbol, moves the head one cell left or right, and enters a new state.

• Finite control. The program has finitely many states, independent of the input length.
• Tape. A one-way infinite sequence of cells, initially holding the input followed by blanks.
• Head. The pointer to the current tape cell. It can read, overwrite, and move left or right.
• Halting states. The accept and reject states stop the computation immediately.

Finite automata read a string once, left to right, and never change it. Turing machines may revisit earlier cells, rewrite symbols, and use blank cells as work space.

Because it can revisit and rewrite cells, a TM can compare the two ends of a string against each other, which a one-pass finite automaton cannot do.

Formal Turing machine. A Turing machine is a 7-tuple

$$M=(Q,\Sigma,\Gamma,\delta,q_0,q_{\text{accept}},q_{\text{reject}})$$

with the following parts:

Symbol	Role
$Q$	finite set of states
$\Sigma$	input alphabet, not containing the blank symbol $\sqcup$
$\Gamma$	tape alphabet, with $\sqcup\in\Gamma$ and $\Sigma\subseteq\Gamma$
$\delta$	transition function
$q_0\in Q$	start state, where computation begins
$q_{\text{accept}}\in Q$	accepting halting state
$q_{\text{reject}}\in Q$	rejecting halting state, with $q_{\text{reject}}\ne q_{\text{accept}}$

Only non-halting states need transitions:

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

If $\delta(q,a)=(r,b,R)$, then in state $q$ reading $a$, the machine writes $b$, moves one cell right, and enters state $r$. The case $\delta(q,a)=(r,b,L)$ is the same except that the head moves left.

At minimum, a TM description must make three distinguished states clear:

State	Role
$q_0$	first state of the computation
$q_{\text{accept}}$	halts with answer yes
$q_{\text{reject}}$	halts with answer no

Extra states are working states used before the machine halts.

State graph of a TM. A directed graph drawing of the transition function: the graph and the 7-tuple describe the same machine. Nodes are states, the incoming arrow marks $q_0$, and an edge label has the form

$$a\to b,D$$

meaning: if the head reads $a$, write $b$, move in direction $D\in\{L,R\}$, and enter the target state.

A complete machine fits in a small graph. Let $M$ decide

$$L=\{w\in\{0,1\}^*\mid w\text{ has no }1\}=0^*,$$

the strings made only of 0s. One working state suffices: stay in $q_0$, walking right over each 0 without changing it, until the head meets the first blank (accept, the input was all 0s) or the first 1 (reject). The blank in this and every later figure is the tape blank $\sqcup$.

Graph feature	Meaning
incoming arrow	start state $q_0$
self-loop on $q_0$	read 0, rewrite it, keep scanning right
double circle	accepting halt $q_{\text{accept}}$
node $q_{\text{reject}}$	rejecting halt
edge label $a\to b,D$	read $a$, write $b$, move $D$

In the graph, $q_{\text{accept}}$ and $q_{\text{reject}}$ are drawn with no outgoing edges.

The input alphabet says what may appear in the original input. The tape alphabet says what the machine may use while computing, including marks such as $X$ and the blank symbol $\sqcup$.

Configurations and Computation

Configuration. A complete snapshot of a Turing machine computation: current state, current head position, and the finite visible part of the tape.

The notation $uqv$, with $u,v\in\Gamma^*$ and $q\in Q$, means the state is $q$, the visible tape content is $uv$ with the head on the first symbol of $v$, and every other cell is blank.

If $u=\epsilon$, the head is on the leftmost tape cell. If $v=\epsilon$, the head scans the blank cell immediately after $u$.

Transition between configurations. Suppose the current configuration is $uaq_i bv$, so the head scans $b$ and $a$ is the symbol immediately to its left.

If $\delta(q_i,b)=(q_j,c,L)$, then the next configuration is

$$uq_jacv.$$

The machine overwrites $b$ by $c$ and moves left, so the head now scans $a$. If $\delta(q_i,b)=(q_j,c,R)$, then the next configuration is

$$uacq_jv.$$

At the left edge, a left move keeps the head on the first cell. At the right edge of the shown word, blank cells are added as needed.

Computation. On input $w\in\Sigma^*$, the starting configuration is $q_0w$. Write $C\vdash C'$ when configuration $C$ yields $C'$ in one step. The machine repeatedly applies valid transitions until it reaches $q_{\text{accept}}$, reaches $q_{\text{reject}}$, or never halts.

Resolving a run. Take the machine $M$ for $0^*$. On input 00 every step is forced, and the run reaches $q_{\text{accept}}$ in three moves:

$$q_0\,00\ \vdash\ 0\,q_0\,0\ \vdash\ 00\,q_0\,\sqcup\ \vdash\ 00\,\sqcup\,q_{\text{accept}}.$$

Each 0 is rewritten as the head steps right; reading the trailing blank in $q_0$ sends $M$ to $q_{\text{accept}}$. The same run reads as one tape per configuration, the scanned cell shown inverted:

A single 1 derails the run. On 01 the first 0 is consumed, but reading the 1 in $q_0$ triggers $q_{\text{reject}}$:

$$q_0\,01\ \vdash\ 0\,q_0\,1\ \vdash\ 0\,1\,q_{\text{reject}}.$$

Unlike a DFA, a Turing machine does not always produce an answer. It may run forever.

An infinite computation does not have to repeat a configuration. The tape can keep changing, or the head can keep moving into fresh blank cells, so there are infinitely many possible configurations. Repetition is forced only when the computation is confined to finitely many configurations.

Recognizers and Deciders

Turing-recognizable language. A language $L\subseteq\Sigma^*$ recognized by some Turing machine $M$: for every input $w$,

1. if $w\in L$, then $M$ accepts $w$;
2. if $w\notin L$, then $M$ rejects $w$ or loops forever.

A recognizer is allowed to fail to answer no.

Turing-decidable language. A language $L\subseteq\Sigma^*$ decided by some Turing machine $M$: for every input $w$, the machine halts, and it accepts exactly when $w\in L$.

Every decidable language is recognizable: a decider is a recognizer that also halts on all no-instances. The converse is not automatic, because looping is not the same as rejecting.

Input type	Recognizer for $L$	Decider for $L$
$w\in L$	must accept	must accept and halt
$w\notin L$	may reject or loop	must reject and halt

Recognition is a semi-answer: yes is reliable, no may never arrive. Decision is a total yes/no algorithm.

Designing Turing-Machine Algorithms

Turing machines are usually designed at a high level. A step such as "scan right until the next unmarked 1" is valid when it can be implemented by finitely many states moving one cell at a time.

Recipe: designing a TM decider.

1. Choose work symbols. Add tape symbols that store progress, such as $X$ for a crossed-off input symbol.
2. Use sweeps. Move left-to-right or right-to-left while a state records the small finite fact needed for the sweep.
3. Maintain an invariant. State what the marks mean after each pass.
4. Separate halting cases. Say exactly when the machine accepts and when it rejects.
5. Prove termination. For a decider, show that every loop makes finite progress toward a halt.

Example 1. Equal numbers of 0s and 1s.

The language $C$ from the opening is not regular, yet it is decidable.

The machine pairs off one 0 with one 1 per sweep until nothing is left. It uses

$$Q=\{q_0,q_1,q_2,q_3,q_A,q_R\},\qquad \Sigma=\{0,1\},\qquad \Gamma=\{0,1,X,\sqcup\},$$

where $q_A=q_{\text{accept}}$ and $q_R=q_{\text{reject}}$ are the halts, $X$ temporarily marks a matched symbol, and $\sqcup$ is the blank. Each edge still reads as $a\to b,D$, with two shorthands: a comma-separated read set fires on any of the listed symbols, and an omitted write leaves the cell unchanged. So $X,0\to R$ means "on $X$ or $0$, leave the cell and move right".

Read the diagram as one repeating loop:

• $q_0$: pick the leftmost symbol. A 0 is erased ($\sqcup$) and the machine remembers "find a 1" by entering $q_1$; a 1 is erased and it enters $q_2$ to find a 0; a leftover $X$ is erased and skipped; a $\sqcup$ means everything is gone, so accept.
• $q_1$ / $q_2$: find the opposite symbol. $q_1$ runs right over 0s and Xs to the first 1, writes $X$, and turns back in $q_3$; $q_2$ is the mirror image. Hitting $\sqcup$ first means the partner is missing, so reject.
• $q_3$: rewind. Walk left over everything until the blank gap on the left, then step right into $q_0$ for the next sweep.

Each completed loop erases one 0 and one 1, so the counts stay equal exactly when the tape empties cleanly into $q_A$.

The run on 0110 is traced configuration by configuration, the scanned cell inverted:

Run on 0110

The invariant is that each completed loop removes exactly one 0 and one 1 (one rewritten to $\sqcup$ in $q_0$, its partner marked $X$ and then erased on the next sweep), so the consumed symbols always hold equally many 0s and 1s. Accepting requires a fully blank tape, which is reachable only when the counts matched; rejecting happens the instant $q_1$ or $q_2$ runs off the end with no partner. Every loop consumes two cells, so the remaining input strictly shrinks and the machine always halts.

The tape converts an unbounded counting problem into a bookkeeping problem: remember progress by writing on the input.

Example 2. Unary powers of two.

Let

$$P=\{0^{2^n}\mid n\ge 0\}.$$

A TM can decide $P$ by repeatedly testing whether the current number of unmarked zeros is even and then deleting half of them.

1. If there are no unmarked zeros, reject.
2. Sweep left to right over the unmarked zeros, alternating between keeping one and marking the next one as deleted.
3. If exactly one unmarked zero was seen during the pass, accept.
4. If an odd number greater than one was seen, reject.
5. If an even number was seen, return to the left end and repeat on the unmarked zeros.

Each non-halting pass divides the number of unmarked zeros by $2$. A positive integer eventually reaches $1$ exactly when it is a power of two; otherwise, some pass reaches an odd number greater than $1$ and rejects. Because the number of unmarked zeros strictly decreases after every non-halting pass, the machine always halts.

Accepted: 0, 00, 0000. Rejected: 000 and 000000; halving six unmarked zeros leaves three, and the next pass sees an odd count greater than one, so it rejects.

The Church-Turing Thesis

Algorithm. An effective finite procedure for solving a problem. Before Turing machines and equivalent models, this was an intuitive idea rather than a formal mathematical object.

Church-Turing thesis. The informal notion of an algorithm coincides with what a Turing machine can compute.

This is not a theorem, because one side is informal. Its force comes from robustness: Turing machines, $\lambda$-calculus, recursive functions, register machines, and ordinary programming languages all define the same class of computable functions. Variants such as multi-tape Turing machines may change efficiency, but not which languages are decidable.

Diophantine equation. A polynomial equation with integer coefficients whose solutions are required to be integers.

For example, $3x^2-2xy-y^2z-7=0$ has the integer solution $x=1$, $y=2$, $z=-2$.

Hilbert's tenth problem asked for an algorithm deciding whether an arbitrary Diophantine equation has an integer solution. Once "algorithm" had a formal meaning, the problem could be answered precisely: Matiyasevich proved in 1970, building on work of Davis, Putnam, and Robinson, that no such algorithm exists.

Turing machines therefore do two jobs at once. They show that simple finite programs with unbounded work tape can decide many non-regular languages, and they provide the language needed to prove that some computational problems have no algorithm at all.