We've been climbing a hierarchy of increasingly powerful machines. DFAs had no memory beyond their current state — good enough for regular languages, but they couldn't count. PDAs added a stack — good enough for context-free languages like \(\{0^n1^n\}\) and palindromes, but limited to LIFO matching. The CF pumping lemma showed that context-free languages have their own walls: \(\{a^nb^nc^n\}\), \(\{ww\}\), and anything requiring cross-serial dependencies.

So what if we remove all restrictions? Give a machine an infinite tape it can read, write, and move on in both directions. No stack discipline — full random access to everything it's written. This is the Turing machine, and it represents the biggest conceptual leap in this entire course.

Picture a machine with three components:

1. An infinite tape divided into cells, stretching infinitely to the right. Each cell holds one symbol. The input string is written on the leftmost cells; everything else is blank.
2. A head that sits over one cell at a time. It can read the symbol, write a new symbol (possibly overwriting the old one), and move one cell left or right.
3. A finite control — a finite set of states, including a start state, an accept state, and a reject state.

Now compare this to a DFA. A DFA also reads a tape left-to-right using a finite control. But a DFA can only read and only move right. Those seem like minor restrictions — but removing them changes everything:

• Writing lets the machine leave itself notes — mark symbols as "seen," convert them, use the tape as scratch paper
• Moving left lets the machine re-examine previous input, shuttle back and forth, compare distant parts of the string

Let's compare this to what we know and unpack what changed:

\(\Sigma\) vs. \(\Gamma\) — two alphabets

A DFA had one alphabet \(\Sigma\). A PDA added a stack alphabet \(\Gamma\). A TM also has two alphabets, but the relationship is different:

• \(\Sigma\) = input alphabet — the symbols that can appear in the input string. Crucially, the blank symbol \(\sqcup\) is not in \(\Sigma\). This is what lets the machine detect the end of the input: it's where the blanks start.
• \(\Gamma\) = tape alphabet — everything that can appear on the tape, including \(\Sigma\) and the blank \(\sqcup\). The tape alphabet often includes extra "marker" symbols like \(\texttt{x}\), \(\dot{0}\), etc., that the machine writes as scratch work.

\(\delta\) — the transition function

Compare to our previous machines:

• DFA: \(\delta: Q \times \Sigma \to Q\) — read a symbol, change state. That's it.
• PDA: \(\delta: Q \times \Sigma_\varepsilon \times \Gamma_\varepsilon \to \mathcal{P}(Q \times \Gamma_\varepsilon)\) — read input (or not), pop (or not), push (or not), nondeterministically.
• TM: \(\delta: Q \times \Gamma \to Q \times \Gamma \times \{L, R\}\) — read tape, write tape, move head. Deterministic (single output, not a set) and total (defined for every state-symbol pair, except at \(q_{\text{accept}}\) and \(q_{\text{reject}}\)).

\(q_{\text{accept}}\) and \(q_{\text{reject}}\) — not a set \(F\)

This is a subtle but important change from DFAs and PDAs. Those machines had a set of accept states \(F \subseteq Q\), and acceptance was determined by which state you ended up in after reading all input. A Turing machine instead has:

• A single accept state \(q_{\text{accept}}\) — entering this state immediately halts the machine and accepts
• A single reject state \(q_{\text{reject}}\) — entering this state immediately halts the machine and rejects
• These must be different: \(q_{\text{accept}} \neq q_{\text{reject}}\)

A configuration captures the complete state of a TM at one moment: the current state, the tape contents, and the head position. We need a compact notation for this.

Configuration yields

We say configuration \(C_1\) yields \(C_2\) (written \(C_1 \vdash C_2\)) if the TM can go from \(C_1\) to \(C_2\) in a single step. Formally:

• Leftward move: If \(\delta(q_i, b) = (q_j, c, L)\), then \(ua\, q_i\, bv \;\vdash\; u\, q_j\, acv\). The head was on \(b\), wrote \(c\), moved left onto \(a\).
• Rightward move: If \(\delta(q_i, b) = (q_j, c, R)\), then \(ua\, q_i\, bv \;\vdash\; uac\, q_j\, v\). The head was on \(b\), wrote \(c\), moved right onto the first symbol of \(v\).

Special configurations:

• Start configuration: \(q_0\, w\) — state \(q_0\), head on the leftmost symbol of input \(w\)
• Accepting configuration: any configuration where the state is \(q_{\text{accept}}\)
• Rejecting configuration: any configuration where the state is \(q_{\text{reject}}\)
• Accepting and rejecting configurations are halting configurations — no further steps are taken

With DFAs and PDAs, there were two possible outcomes: accept or reject. A Turing machine introduces a third possibility that changes everything:

"Looping" doesn't necessarily mean the machine cycles through the same states — it can exhibit complex, non-repeating behavior while still never reaching a halting state. And here's the devastating fact: given an arbitrary TM and input, there is in general no way to tell whether the machine will eventually halt or loop forever. (That's the halting problem — coming in a later page.)

The three-outcome possibility forces us to make a distinction that didn't exist before:

Sipser identifies three levels of description for Turing machines, from most to least formal. This is important because you'll use different levels in different contexts:

Level 1: Formal description

The complete 7-tuple plus the full transition function \(\delta\) (as a table or state diagram). This is what you'd need to actually build the machine. We give formal descriptions for the first few examples, but they're unwieldy even for simple languages.

Level 2: Implementation description

English prose describing the head movements, what gets written, and state transitions — but at the level of tape operations. "Scan right until you find a blank" or "mark the current symbol with an x and move left to the beginning." This is the most common level for exam answers.

Level 3: High-level description

Plain English algorithm with no mention of the tape, head, or states. "Sort the input and check if adjacent elements are equal." Sipser uses this for most examples, writing \(M = \)"On input \(w\): ..." followed by numbered steps.

TM state diagrams look like DFA diagrams with one key difference in transition labels:

Other conventions:

• \(q_{\text{accept}}\) and \(q_{\text{reject}}\) are drawn as labeled nodes (sometimes with double circles for accept). Often \(q_{\text{reject}}\) and its transitions are omitted for clarity — any missing transition implicitly goes to \(q_{\text{reject}}\).
• Multiple transitions from the same state can be combined: 0,1 → R means "on reading 0 or 1, don't change it, move right."

We already built a PDA for this language (page 10). The PDA used a stack to count: push 0s, pop on 1s. A TM takes a completely different approach — it has no stack, but it has a writable tape. The strategy is to match pairs by marking them off.

High-level description

\(M_1 = \) "On input \(w\):

1. Scan across the tape. If the tape contains symbols after the first \(\sqcup\), or if any \(0\) appears to the right of any \(1\), reject.
2. If the tape is empty (first symbol is \(\sqcup\)), accept.
3. Cross off the leftmost remaining \(0\) (replace with \(\texttt{x}\)) and scan right to cross off the leftmost remaining \(1\) (replace with \(\texttt{x}\)).
4. Move the head back to the leftmost remaining \(0\) and go to step 3.
5. If all \(0\)s have been crossed off: scan right — if any \(1\)s remain, reject; otherwise, accept."

Implementation-level description

Simplified version (assumes input is in \(0^*1^*\) form):

1. If head reads \(\sqcup\), accept (empty string).
2. If head reads \(0\): write \(\texttt{x}\), move right.
3. Scan right past \(0\)s and \(\texttt{x}\)s until finding a \(1\). If you hit \(\sqcup\) first, reject (more 0s than 1s).
4. Replace the \(1\) with \(\texttt{x}\), then scan left back to the first \(\texttt{x}\) followed by a \(0\) (or the leftmost position).
5. If head reads \(0\), go to step 2. If head reads \(\texttt{x}\), scan right: if you see a \(1\), reject (more 1s than 0s). If you reach \(\sqcup\), accept.

Trace on input 0011

The key insight: the machine makes \(n\) passes across the tape, crossing off one \(0\)-\(1\) pair each time. Each pass costs \(O(n)\) steps, so the total is \(O(n^2)\). Not efficient — but correct! TMs are about computability, not efficiency.

This language is not context-free — a PDA has no way to compare two arbitrary strings separated by a \(\#\). (The stack would need to be read forward and backward simultaneously.) A TM handles it by zig-zagging: mark a symbol on the left, scan right past \(\#\), check that the corresponding symbol on the right matches, scan back, repeat.

High-level description (Sipser Example 3.9)

\(M_1 = \) "On input \(w\):

1. Zig-zag across the tape to corresponding positions on either side of \(\#\), checking that these positions match. Cross off symbols as they're checked.
2. When all symbols to the left of \(\#\) have been crossed off, check for any remaining symbols to the right of \(\#\). If any remain, reject; otherwise, accept."

Formal description

\(M_1 = (Q, \Sigma, \Gamma, \delta, q_1, q_{\text{accept}}, q_{\text{reject}})\) where \(Q = \{q_1, \ldots, q_8, q_{\text{accept}}, q_{\text{reject}}\}\), \(\Sigma = \{0, 1, \#\}\), and \(\Gamma = \{0, 1, \#, \texttt{x}, \sqcup\}\).

State diagram

Reading the diagram:

• \(q_1\): Start state. Read current symbol: if \(0\), replace with \(\texttt{x}\) and enter \(q_2\) (remembering we need to match a 0). If \(1\), replace with \(\texttt{x}\) and enter \(q_3\) (remembering we need to match a 1). If \(\#\), go to \(q_8\) to verify right side is empty too.
• \(q_2\)/\(q_3\): Scan right past \(0\)s, \(1\)s, and past \(\#\), then past \(\texttt{x}\)s, looking for the first uncrossed symbol on the right side.
• \(q_4\)/\(q_5\): Verify the match (must be 0 or 1 respectively). Cross it off with \(\texttt{x}\).
• \(q_6\)/\(q_7\): Scan left all the way back to the first \(\texttt{x}\) on the left side, then move right to the next uncrossed symbol.
• \(q_8\): All left symbols matched — scan right past \(\#\) and \(\texttt{x}\)s to verify nothing remains. If \(\sqcup\), accept.

Trace on input 01#01

This is the language of strings of 0s whose length is a power of 2: \(\{0, 00, 0000, 00000000, \ldots\}\). Neither DFAs nor PDAs can handle this — a DFA can't count at all, and a PDA's stack can check linear relationships but not exponential ones. This example showcases the true power of a writable tape.

High-level description (Sipser Example 3.7)

\(M_2 = \) "On input \(w\):

1. Sweep left to right across the tape, crossing off every other \(0\).
2. If in stage 1 the tape contained a single \(0\), accept.
3. If in stage 1 the tape contained more than one \(0\) and the number of \(0\)s was odd, reject.
4. Return the head to the left-hand end of the tape.
5. Go to stage 1."

Each sweep halves the number of \(0\)s. If the original count was a power of 2, repeated halving will reach exactly 1. If not, some sweep will encounter an odd count greater than 1, and the machine rejects.

Formal description

\(M_2 = (Q, \Sigma, \Gamma, \delta, q_1, q_{\text{accept}}, q_{\text{reject}})\) where:

• \(Q = \{q_1, q_2, q_3, q_4, q_5, q_{\text{accept}}, q_{\text{reject}}\}\)
• \(\Sigma = \{0\}\)
• \(\Gamma = \{0, \texttt{x}, \sqcup\}\)

State diagram

How the states work:

• \(q_1\): Initial entry point. Write \(\sqcup\) over the leftmost 0 (marking the left end of tape), move right to \(q_2\). This blank serves as a left-end marker so the machine can find its way back.
• \(q_2\): The "crossing off" state for even-positioned 0s. Skip this 0 (leave it), move right to \(q_3\).
• \(q_3\): Cross off this 0 (write \(\texttt{x}\)), move right. If you see \(\sqcup\) (end of input), check whether you just crossed off the only one — if so, the count was odd (reject unless count was 1). Go back to \(q_5\) and return to start.
• \(q_5\): Sweep left until finding the left-end blank. Move right to \(q_2\) and start the next halving pass.

Trace on input 0000 (\(n = 2\), length = \(2^2 = 4\))

If the input were \(000\) (length 3, not a power of 2): 3 is odd, so the first sweep detects an odd count > 1 and rejects immediately.

Just as we studied NFA variants of DFAs, there are variants of Turing machines. The remarkable result is that none of them add computational power — they all recognize the same class of languages.

Nondeterministic Turing Machines (NDTM)

A nondeterministic TM has a transition function \(\delta: Q \times \Gamma \to \mathcal{P}(Q \times \Gamma \times \{L, R\})\) — at each step, multiple transitions may be possible. The computation branches into a tree. The NDTM accepts if any branch reaches \(q_{\text{accept}}\).

Multitape Turing Machines

A \(k\)-tape TM has \(k\) separate infinite tapes, each with its own head. The transition function reads all \(k\) heads simultaneously and can write to all tapes and move all heads independently: \(\delta: Q \times \Gamma^k \to Q \times \Gamma^k \times \{L, R, S\}^k\) (where \(S\) = stay).

We've now seen that multiple TM variants — multitape, nondeterministic, two-way infinite tapes, enumerators (covered in Decidability) — all recognize exactly the same class of languages. No reasonable enhancement to the model adds computational power. This is remarkable: unlike the DFA-to-PDA-to-TM jumps, where each new model was strictly more powerful, once we reach Turing machines, we're stuck. There's no "level above" that computes more.

This observation, combined with equivalent formalisms developed independently (Alonzo Church's \(\lambda\)-calculus, Emil Post's production systems, recursive functions), leads to one of the most important ideas in computer science: