REFERENCE SHEET

Turing machines, deciders & recognizers

Distinguish computing an answer eventually from guaranteeing an answer on every input.

Before this Finite automata & regular languages, Recursion, invariants & termination

decidable = recognizable ∩ co-recognizable

Definitions

Turing machine

A finite control with an unbounded tape, a read/write head, and a transition rule. Inputs, machine descriptions, and outputs can all be encoded as finite strings.

Decider

A machine that halts on every input, accepting exactly the strings in its language.

Recognizer

A machine that accepts every member and never accepts a nonmember. On a nonmember it may reject or run forever.

Key theorems

Two recognizers give a decider

A language is decidable iff both it and its complement are recognizable. For the reverse direction, dovetail their recognizers until one accepts.

Universal simulation

A Turing machine can simulate a machine supplied as an encoded input together with its input string.

Model robustness

Standard single-tape and multitape Turing machines compute the same partial functions, though their time costs can differ. The Church–Turing thesis identifies this formal notion with effective computation; it is a thesis, not a formal theorem about an independently defined physical universe.

Notable applications

Programming languages

General-purpose programs can be studied through a precise abstract machine model.

Search procedures

Enumerating possible witnesses can recognize a property even when no terminating rejection procedure exists.

Work it out

Try before revealing

01 / Construct

If R recognizes L and S recognizes its complement, describe a decider for L.

Hint

Do not run one recognizer to completion before starting the other.

Solution

Alternate one simulation step of R and one of S on the input. Exactly one must eventually accept. Accept if R does; reject if S does.

02 / Classify

Is acceptance of a supplied Turing machine on a supplied input recognizable?