4.1 Turing Machines, Recognizability, and Decidability: Drawing a Boundary for Algorithmic Power

In the first three chapters, we progressed from finite automata to pushdown automata, gradually increasing the machine’s storage capacity. What if we add to that model a single, infinitely extendable tape that can be read and written upon? What kind of universal computation could such a machine express? More fundamentally, even with a Turing machine as a general-purpose computational model, why does no algorithm exist that can determine the behavior of every program and its input?

Learning Objectives

• Describe the components of a single-tape deterministic Turing machine and its one-step computation;
• Distinguish between acceptance, rejection, and non-halting;
• Differentiate between Turing-recognizable languages and decidable languages;
• Understand the significance of universal machines and the Church–Turing thesis.

1. A Common Seven-Tuple Definition

A deterministic single-tape Turing machine can be defined as:

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

• $Q$: a finite set of states;
• $\mathrm{\Sigma }$: the input alphabet, not containing the blank symbol;
• $\mathrm{\Gamma }$: the tape alphabet, containing both $\mathrm{\Sigma }$ and the blank symbol;
• $\delta$: the transition function;
• $q_0$: the initial state;
• $q_{accept}$ and $q_{reject}$: distinct halting states.

For non-halting states, one definition is:

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

At each step, the machine reads the symbol in the current cell, writes a new symbol, moves one cell left or right, and transitions to a new state. Some textbooks allow the read/write head to remain stationary or use a one-way infinite tape; these variants can be encoded appropriately without altering computational power.

2. Configuration Describes a Complete Snapshot

Knowing only the control state is insufficient, we must also know the contents of the tape and the position of the read/write head. Together, these three elements constitute the configuration. A transition transforms one configuration into the next:

Current state + Read/write head position + Current finite nonblank tape contents
                         ↓ δ
Next state + Tape after writing + Moved read/write head position

For finite input, the rest of the tape is initially blank. At any finite time, only finitely many cells have been visited. During a nonhalting computation, that region can keep growing without a fixed finite bound. An unbounded theoretical tape does not allocate infinite memory instantaneously.

3. A Palindrome Decision Process

To determine whether a binary string is a palindrome, we can design a high-level sequence of steps:

1. If no unmarked character remains, accept; otherwise remember and mark the leftmost one;
2. If no other unmarked character remains, accept: the last character was an odd-length center. Otherwise move to the rightmost unmarked character;
3. Compare the two; if they differ, reject; if they match, mark the right character;
4. Return to the left, repeat;
5. If no unpaired characters remain, accept.

Empty and one-character strings are accepted. For 010, remove the two outer 0 symbols, then accept the central 1; 011 is rejected on the first comparison. The finite control only needs to remember whether the current left endpoint is 0 or 1, while the tape stores the positions that have already been processed. This algorithm may scan the input multiple times and is not time-efficient, yet it halts on every finite input and produces the correct answer, making it a decider.

In the study of computability within Turing machine theory, the model does not need to be directly implemented as a physical system. Multitape Turing machines, standard random-access machines, and Turing-complete languages without predetermined finite resource limits compute the same class of computable functions under suitable encodings. However, complexity conversions still require separate analysis.

4. Accept, Reject, and Non-termination Are Three Possible Outcomes

For an input $w$, a Turing machine may:

• Enter state $q_{accept}$;
• Enter state $q_{reject}$;
• Continue running indefinitely.

If the machine eventually accepts if and only if $w\in L$, then it recognizes the language $L$. For inputs $w\notin L$, the recognizer may either reject or simply never halt.

If the machine halts on every input (accepting members of $L$ and rejecting non-members) then it decides the language $L$.

Thus:

$$\text{Decidable languages}⊊\text{Turing-recognizable languages}.$$

Decidable languages are also known as recursive languages; Turing-recognizable languages are commonly referred to as recursively enumerable languages. Terminology across different sources can be confusing, so it's essential to align definitions when reading materials.

5. Enumerators and Recognizers

An enumerator can output strings as it runs. To enumerate $L$, it must output only members of $L$, with every member appearing at some finite time. Order and repetition usually do not matter. An infinite language has no final moment when the entire list is complete.

A language is recognizable by a Turing machine if and only if it can be enumerated by some enumerator. Intuitively:

• From recognizer to enumerator: simulate all inputs in interleaved scheduling, outputting those that are accepted;
• From enumerator to recognizer: continuously run the enumerator, and accept as soon as the target input appears.

For example, in round $t$, advance each of the first $t$ input simulations by one step. Every started simulation continues to get turns, while each round does finite work. Interleaved scheduling matters. If inputs are processed one at a time in sequence, the simulation might get stuck on the first non-halting one, and no further inputs will ever get a chance to be processed.

6. Universal Turing Machine

Both programs and inputs can be encoded as strings. A universal Turing machine $U$ receives $⟨M,w⟩$ and simulates the execution of machine $M$ on input $w$. This turns "machines" into data, making it the theoretical foundation behind interpreters, virtual machines, and stored-program computers.

Universality does not mean that all problems can be solved. It means that a single fixed machine can simulate any effectively encoded Turing machine; the next lesson will prove that certain questions about the behavior of such machines cannot be answered by any decision procedure.

7. The Church–Turing Thesis Is Not a Theorem

The Church–Turing thesis asserts that any function intuitively regarded as "effectively computable" can be computed by a Turing machine. It bridges an informal conceptual idea with a formal mathematical model, and thus cannot be proven within the same formal system as a standard logical proposition.

Support for the thesis comes from the convergence of multiple independent computational models (such as lambda calculus, recursive functions, and register machines) each arriving at the same class of computable functions. The thesis does not claim that Turing machines are the most efficient model, nor does it impose constraints on the physical architecture of real machines.

Common Misconceptions

• A recognizer always outputs yes/no: Non-members may cause infinite loops during input processing.
• Infinite tape implies infinite memory usage in a single computation: Each halting computation only accesses a finite number of cells.
• A universal machine can solve all input problems: It can simulate any program, but that doesn't mean it can determine all properties of programs.
• The Church–Turing thesis proves that no other physical computation exists in the real world: It is a statement about effective computability, not a complete proof of physical laws.

Exercise

1. Explain why a DFA is always a decider, while a general Turing machine recognizer is not necessarily so.
2. Write high-level decision steps for a Turing machine that recognizes the language $\{0^n{1}^n\mid n\ge 0\}$.
3. Explain why interleaved simulation is necessary in the construction of an enumerator.
4. Compare the differences between a PDA stack and a Turing machine tape in terms of accessible positions.

Summary

A Turing machine combines a finite control with a writable work space, capturing the computational power typically associated with algorithms. Check whether it rejects nonmembers or may run forever. A silent recognizer may still be following its contract; its caller cannot interpret that silence as false.

The next lesson uses the fact that "a program can serve as input" to construct self-reference, proving that the halting problem is undecidable, and learns how the direction of reduction determines whether a proof is valid.