Turing machines, decision procedures, and recognition

Prerequisites: Finite automata, strings, algorithms, and termination arguments.

Learning objectives

• Describe a Turing-machine configuration and transition.
• Distinguish decidable and recognizable languages.
• Explain why simulation requires a fair schedule.

A model with expandable working memory

A Turing machine has finite control and a tape of cells containing symbols, with a head that can read, write, and move. A configuration records the current state, tape contents, and head position. A transition depends on the current state and scanned symbol, changes the symbol and state, and moves the head according to the chosen model. Equivalent variants may use several tapes or different movement conventions.

The tape is not required to be infinitely filled before computation begins. Any finite execution visits only finitely many cells, but the model imposes no fixed upper bound on how many cells a sufficiently long computation may use. This separates it from a fixed finite automaton. Real computers have finite memory; the abstract model studies algorithms independent of one machine's particular hardware limit.

Deciding includes a termination promise

A decider halts on every input and answers membership correctly. A recognizer must accept every member eventually and must never accept a nonmember, but it may reject or run forever on nonmembers. These are different guarantees. Observing a simulation for a long time without acceptance cannot establish that acceptance will never happen.

For example, the language of encodings of machines together with inputs on which they eventually halt is recognizable. Simulate the encoded machine; if it halts, accept. For a nonhalting computation, this recognizer keeps simulating forever. The construction does not provide a decider because it supplies no finite stopping rule for the negative case.

Fair interleaving combines searches

Suppose a language and its complement each have recognizers. Run one step of the first, then one step of the second, repeating. If the first accepts, answer yes; if the second accepts, answer no. Every input belongs to exactly one side, so one recognizer eventually accepts. The combined machine therefore decides the language.

Running the first recognizer to completion before starting the second would fail when the first loops. The interleaving must be fair: neither process may be postponed forever. This is often called dovetailing. It appears in proofs involving searches over many possible witnesses and has a practical cousin in scheduling concurrent work.

Models must be interpreted carefully. The Church-Turing thesis identifies effectively computable procedures with Turing-computable ones; it is a thesis about the intended notion of computation, not a theorem proved merely by defining a machine. Computability also says nothing about practical speed. An algorithm can halt on every finite input while requiring resources far beyond any feasible implementation.

Practice problem

You have recognizers R and S for two languages A and B. Design a recognizer for their union without assuming either recognizer halts on a negative input. Describe the scheduler precisely enough to rule out starvation. Then explain whether this construction decides the union. Finally, suppose S recognizes the complement of A instead. Explain how the same scheduling idea produces a decider and identify the property that now guarantees termination.

Worked solution

Maintain separate simulated configurations of R and S on the input. Advance R by one step, then S by one step, repeating indefinitely unless either accepts; at that point accept the union. Rejecting simulations can simply be marked finished while the other continues. If the input belongs to A or B, the corresponding recognizer receives arbitrarily many steps and eventually accepts. If it belongs to neither, both may loop, so this is not necessarily a decider. When S recognizes the complement of A, every input belongs to exactly one recognized side. Accept when R accepts and reject when S accepts. Fair scheduling ensures the appropriate accepting computation eventually receives enough steps. The complementary coverage, not merely the existence of two programs, establishes total termination.

Check your understanding

A recognizer has run for a billion steps without accepting. What follows?

• The input is definitely outside the language.
• The language is undecidable.
• No membership conclusion follows from elapsed steps alone.

Explanation

The recognizer may accept later. A finite timeout is not a proof of nonmembership.

If a language and its complement are both recognizable, what follows?

• The language is decidable by fair interleaving.
• Neither recognizer can ever loop.
• The language must be finite.

Explanation

One recognizer must eventually accept each input, so alternating their steps gives a terminating decision procedure.

Primary reading

• Automata, Computability, and Complexity: MIT OpenCourseWare

Open the study and save your work →