Chapter 4 - Turing Machines

Finite automata are limited by their inability to write or re-read parts of their input; their memory is confined to their current state. To model the full power of computation, we need a more powerful machine. This chapter introduces the Turing Machine (TM), the foundational, abstract model of a general-purpose computer.

4.1 Aims

The goal of this chapter is to introduce the Turing machine as the standard theoretical model for algorithms. While real programming languages are too complex for formal proofs of non-existence, and finite automata are too weak, the Turing machine strikes the perfect balance. It is simple enough for rigorous analysis yet powerful enough to perform any computation that a real computer can. This model will serve as the basis for our study of both computability (what can be computed) and complexity (what can be computed efficiently).

4.2 Excerpt from History

The Turing machine was not conceived to model a physical computer. In the 1930s, Alan Turing sought to formalize the intuitive notion of an “algorithm” or “effective method.” He did this by modeling the process of a human mathematician working on a problem:

• The mathematician has a finite mental state.
• They work with a pencil and paper, which is effectively unlimited.
• In each step, they observe a limited number of symbols and, based on their mental state, write a new symbol and shift their attention.

Turing abstracted this process into a machine with:

1. A finite control (the set of states).
2. An infinite tape (the paper), divided into cells.
3. A read/write head that can move along the tape.

This simple, powerful model became the cornerstone of theoretical computer science.

4.3 The Model of the Turing Machine

A Turing machine is a generalization of a finite automaton.

Components of a Turing Machine

An informal view of a TM includes:

1. A finite control, which contains the program and is always in one of a finite number of states.
2. An infinite tape, which serves as both input, output, and memory. It is bounded on the left by a special symbol $\text{textcent}$ and is infinite to the right. The tape is initialized with the input string, followed by infinite blank symbols $\bigsqcup$.
3. A read/write head, which can read a symbol from the tape, write a new symbol in its place, and move one cell to the left or right.

Formal Definition

Definition 4.1: Turing Machine (TM)

A Turing Machine (TM) is a 7-tuple $M=(Q,\Sigma ,\Gamma ,\delta ,q_0,q_{accept},q_{reject})$, where:

1. $Q$ is a finite set of states.
2. $\Sigma$ is the input alphabet, which does not contain the blank symbol $\bigsqcup$.
3. $\Gamma$ is the tape alphabet, where $\Sigma \subseteq \Gamma$ and $\bigsqcup ,⊢\in \Gamma$.
4. $\delta :(Q\setminus \{q_{accept},q_{reject}\})\times \Gamma \to Q\times \Gamma \times \{L,R\}$ is the transition function.
5. $q_0\in Q$ is the start state.
6. $q_{accept}\in Q$ is the accept state.
7. $q_{reject}\in Q$ is the reject state, where $q_{reject}\ne q_{accept}$.

The transition function $\delta (q,a)=(p,b,D)$ dictates the machine’s behavior: if in state $q$ reading symbol $a$, the machine transitions to state $p$, writes symbol $b$, and moves the head in direction $D\in \{L,R\}$ (Left/Right).

Dynamics of a Turing Machine

• Configuration: A snapshot of the TM’s status is captured by a configuration. We represent it as $uqv$, where $q$ is the current state, $u$ is the tape content to the left of the head, and $v$ is the content from the head’s position to the right.
• Step: The relation ${⊢}_M$ describes a single computation step. For example, if $\delta (q,b)=(p,c,R)$, then $uaqb{u}^{\prime }{⊢}_{M}uacp{u}^{\prime }$.
• Computation: A sequence of configurations starting from the initial configuration $q_0⊢w$.
• Halting: The machine halts if it enters $q_{accept}$ or $q_{reject}$. If it enters $q_{accept}$, it accepts the input. If it enters $q_{reject}$, it rejects. It is also possible for a TM to never halt, i.e., to loop.

Languages and Computability

This leads to two crucial classes of languages:

• Recursively Enumerable ($L_{RE}$): A language $L$ is recursively enumerable if there is a TM $M$ such that $L(M)=L$. For any $w\in L$, $M$ halts and accepts. For $w\notin L$, $M$ either rejects or loops forever. These are also called Turing-recognizable languages.
• Recursive ($L_R$): A language $L$ is recursive if there is a TM $M$ that halts on all inputs and $L(M)=L$. Such a TM is called a decider. These are also called decidable languages.

Deciders vs. Recognizers

Every recursive language is recursively enumerable, but not vice-versa. The ability to always halt is a much stronger condition. A decider gives you a definite yes/no answer for any input. A recognizer only guarantees a “yes” for strings in the language; for others, you might wait forever.

4.4 Multi-tape Turing Machines and the Church-Turing Thesis

A single-tape TM can be cumbersome for designing algorithms. A more convenient and realistic model is the Multi-tape Turing Machine (MTM). An MTM has a read-only input tape and $k$ read/write work tapes, each with its own independent head.

A transition depends on the current state and the symbols read by all $k+1$ heads. In one step, it can change state, write to all $k$ work tapes, and move each head independently.

Equivalence of TM Models

For every multi-tape Turing machine, there is an equivalent single-tape Turing machine.

Proof Sketch: We can simulate a $k$-tape MTM with a single-tape TM. The single tape is formatted to have $2k$ “tracks”. For each work tape of the MTM, we use one track to store its content and another track to mark the head position with a special symbol. To simulate one step of the MTM, the single-tape TM makes a full sweep across its tape to read all the relevant symbols, and another sweep to update the contents and head positions. This simulation incurs a polynomial slowdown (specifically, quadratic), but it preserves the fundamental computability.

The Church-Turing Thesis

The remarkable robustness of the Turing machine model—the fact that all reasonable, alternative models of computation (lambda calculus, register machines, etc.) have been proven equivalent in power—leads to a foundational principle of computer science.

The Church-Turing Thesis

The intuitive notion of an algorithm is equivalent to the formal model of a Turing machine that always halts.

This is not a mathematical theorem because “intuitive notion” is not a formal definition. It is an axiom we accept based on overwhelming evidence. It asserts that any problem that can be solved by any computational procedure can be solved by a Turing machine.

4.5 Nondeterministic Turing Machines

Like FAs, we can introduce nondeterminism to Turing machines. A Nondeterministic Turing Machine (NTM) has a transition function that maps a state-symbol pair to a set of possible transitions.

An NTM accepts an input if at least one of its possible computation paths leads to the accept state. The computation can be visualized as a tree of configurations.

Equivalence of NTMs and DTMs

For every Nondeterministic Turing Machine, there is an equivalent Deterministic Turing Machine.

Proof Sketch: A DTM can simulate an NTM by systematically exploring its computation tree using a breadth-first search (BFS). The DTM uses its tape to keep track of all possible configurations the NTM could be in at a given step. It explores all paths of length 1, then all paths of length 2, and so on. If it ever finds a configuration with an accepting state, it accepts.

The Exponential Cost of Simulating Nondeterminism

While DTMs can simulate NTMs, the simulation may require exponentially more time. If an NTM solves a problem in $t(n)$ steps, the simulating DTM might take $O(c^{t(n)})$ steps for some constant $c$. Whether this exponential blow-up is necessary is the essence of the famous P vs. NP problem.

4.6 Encoding of Turing Machines

A crucial feature of Turing machines is that they can be described by a finite string of symbols. We can devise a standardized encoding scheme, Kod(M), to represent any TM $M$ as a unique binary string.

This allows us to treat Turing machines themselves as input to other Turing machines. This concept of a Universal Turing Machine—a TM that takes the encoding of another TM $M$ and an input $w$ and simulates the computation of $M$ on $w$—is the theoretical basis for the stored-program computers we use today.

4.7 Summary

• The Turing Machine is a simple yet powerful model that captures the essence of general-purpose computation.
• It defines two key classes of languages: recursively enumerable (solvable by a TM that might loop) and recursive (solvable by a TM that always halts).
• The Church-Turing Thesis posits that any problem solvable by an algorithm is solvable by a Turing machine.
• Variants like multi-tape and nondeterministic TMs do not increase the fundamental power of the model (what can be computed), but they can dramatically affect the efficiency (the resources required).
• The simulation of nondeterminism by determinism may incur an exponential time cost, a central theme in complexity theory.
• Turing machines can be encoded as strings, allowing them to be processed as data by other machines.