09 Turing Machines

Lecture from: 14.10.2025 | Video: Videos ETHZ

From Finite Automata to a Universal Model

We’ve explored the world of finite automata and seen their limitations. While they are excellent for recognizing regular patterns, they fail on languages that require unbounded counting, like our canonical example $L=\{a^k{b}^k\mid k\in \mathbb{N}\}$.

To solve such problems, we need a more powerful model of computation. We need a machine that isn’t limited by a finite number of states as its only form of memory. This brings us to the central concept of this course: the Turing Machine.

This model was conceived by Alan Turing in 1936, remarkably, before the existence of modern digital computers. He wasn’t trying to build a physical machine; he was trying to formalize the very essence of what it means for a human “computer” (a person performing calculations) to follow a mechanical procedure.

The Intuition: A Human with Paper

Imagine a mathematician performing a calculation, like long multiplication, following a set of rules learned in school. What happens in a single step?

• They read a constant number of symbols (e.g., two digits).
• They perform a calculation in their head (applying a rule).
• They find a place on the paper to write the result.
• They might keep a small, constant-sized piece of information in their head (like a carry digit).

Turing abstracted this process. He imagined a machine with two key components:

1. A finite control: This is like the mathematician’s brain. It contains a finite set of rules and can be in one of a finite number of internal “states of mind.”
2. An infinite tape: This is the paper. It’s an infinitely long strip, divided into cells, each capable of holding one symbol. This provides the machine with unbounded memory.

The machine interacts with the tape via a read/write head.

In a single step, the Turing machine:

1. Reads the symbol under the head.
2. Based on its current state and the symbol it read, it consults its transition function (its “program”).
3. This function tells it to:
   1. Write a new symbol onto the tape cell it’s currently on.
   2. Move the head one cell to the left (L), one cell to the right (R), or not at all (N).
   3. Change to a new internal state.

This simple model, with its ability to both read and write on an infinite tape and move back and forth, is powerful enough to capture the full notion of “algorithm.”

Formal Definition of a Turing Machine

A Turing Machine (TM) is formally defined as a 7-tuple:

$$M=(Q,\Sigma ,\Gamma ,\delta ,q_0,q_{acc},q_{rej})$$

1. $Q$: A finite set of states, just like in a DFA.
2. $\Sigma$: The input alphabet. These are the symbols the initial input word is made of.
3. $\Gamma$: The tape alphabet (or working alphabet). This is the set of all symbols that can be written on the tape. It must include the input alphabet ($\Sigma \subseteq \Gamma$). It also contains two special symbols:
   • ⊔ (or □): The blank symbol, which fills the infinite tape beyond the input.
   • $ (or ⊳): The start symbol or left-end marker, which marks the beginning of the tape.
4. $q_0\in Q$: The start state.
5. $q_{acc}\in Q$: The unique accept state.
6. $q_{rej}\in Q$: The unique reject state.
7. $\delta$: The transition function. This is the heart of the machine. It maps a state and a tape symbol to a new state, a new tape symbol, and a head movement. $$\delta :(Q\setminus \{q_{acc},q_{rej}\})\times \Gamma \to Q\times \Gamma \times \{L,R,N\}$$ Note that once the machine enters an accept or reject state, its computation halts; there are no transitions out of them.

How a Turing Machine Computes

Configurations

A configuration of a TM is a snapshot of its entire state: the contents of the tape, the position of the head, and the current state of the finite control. We can represent this crisply as a string. For a tape containing ...$x_1...x_i...x_n..., with the machine in state $q$ and the head over symbol $x_i$, we write the configuration as:

$$\$x_1\dots x_{i-1}q{x}_i{x}_{i+1}\dots x_n$$

The state symbol is placed just before the symbol the head is currently scanning.

• Start Configuration: For an input word $w\in {\Sigma }^{\ast }$, the computation begins in the configuration q_0 \ w$.

Steps and Computations

A step is a transition from one configuration to another, denoted by ${⊢}_M$. The rules depend on the head movement specified by $\delta$.

• Neutral Move (N): If $\delta (q,x_i)=(p,Y,N)$, the machine writes $Y$ and stays put. $$\$x_1\dots x_{i-1}q{x}_i{x}_{i+1}\dots x_n{⊢}_M\$x_1\dots x_{i-1}pY{x}_{i+1}\dots x_n$$
• Left Move (L): If $\delta (q,x_i)=(p,Y,L)$, the machine writes $Y$ and moves left. $$\$x_1\dots x_{i-2}{x}_{i-1}q{x}_i\dots x_n{⊢}_M\$x_1\dots x_{i-2}p{x}_{i-1}Y\dots x_n$$
• Right Move (R): Analogous to the left move.

A computation is a sequence of configurations $C_0,C_1,C_2,\dots$ where $C_i{⊢}_M{C}_{i+1}$ for all $i\ge 0$. We use ${⊢}_M^{\ast }$ for the reflexive, transitive closure (“reaches in zero or more steps”).

Halting and Outcomes

Unlike a DFA, which always halts after reading the input, a TM’s computation might never end. It could loop forever. This leads to three possible outcomes for any given input word:

1. Accept: The computation reaches a configuration containing the state $q_{acc}$.
2. Reject: The computation reaches a configuration containing the state $q_{rej}$.
3. Loop: The computation never reaches $q_{acc}$ or $q_{rej}$ and continues indefinitely.

Languages and Functions of Turing Machines

Recognizing Languages

• The language accepted by a TM $M$, denoted $L(M)$, is the set of all input words for which the computation of $M$ halts in the accept state. $$L(M)=\{w\in {\Sigma }^{\ast }\mid q_0\$w{⊢}_M^{\ast }{w}_1{q}_{acc}{w}_2\text{ for some }{w}_1,w_2\in {\Gamma }^{\ast }\}$$
• A language $L$ is called recursively enumerable (or Turing-recognizable) if there exists a TM $M$ such that $L=L(M)$. We denote this class of languages as ${\mathcal{L}}_{RE}$.
• A language $L$ is called recursive (or decidable) if there exists a TM $M$ that always halts on every input, and $L=L(M)$. This is a stronger condition. We denote this class as ${\mathcal{L}}_R$.

Computing Functions

A TM can also be used to compute a function $F:{\Sigma }_1^{\ast }\to {\Sigma }_2^{\ast }$. We say a TM $M$ computes $F$ if for every input $x$, the machine halts in the accept state with the tape containing just \F(x)$.

$$\text{For all }x\in {\Sigma }_1^{\ast }:q_0\$x{⊢}_M^{\ast }{q}_{acc}\$F(x)$$

A function is called total computable if such a halting TM exists for it.

Example: $L=\{0^n{1}^n\mid n\ge 1\}$

We know this language is not regular. Let’s sketch how a Turing machine could decide it.

Input on tape: $...$000111...

High-level Algorithm:

1. Move the head to the first 0. Replace it with a special symbol, say A.
2. Move the head right, past all the 0s and 1s, until you find the last 1.
3. Replace that 1 with another special symbol, say B.
4. Move the head back to the left until you find the leftmost A.
5. Move one step right to the next 0.
6. Repeat the process: change the 0 to an A, find the rightmost 1, change it to a B, and return.

Outcomes:

• If, while searching for a 1 to match a 0, you find no more 1s, there were too many 0s. Reject.
• If, after matching all the 0s, you scan left and find there are still unmatched 1s on the tape, there were too many 1s. Reject.
• If, after changing the last 0 to an A, you find no more 1s to match it with, and there are also no 0s left, then the counts were equal. Accept.

This back-and-forth process, using the tape as both input and scratch memory, is something a DFA could never do. It demonstrates the fundamental power gained from having a read/write head on an infinite tape.