GIVEN A TURING MACHINE M AND AN INPUT w, EXACTLY ONE OF THREE THINGS HAPPENS: 1. M ACCEPTS w — it reaches an accepting state and halts. 2. M REJECTS w — it halts in a non-accepting state, or with no applicable transition. 3. M LOOPS ON w — it never halts. THE LANGUAGE OF M is defined by the first outcome only: L(M) = { w : M accepts w } NOTE WHAT THIS DEFINITION DOES **NOT** SAY. It says nothing about M's behaviour on strings outside L(M) — they may be rejected or may cause an infinite loop, and the language is the same either way. THAT ASYMMETRY IS DELIBERATE AND IS THE SOURCE OF THE ENTIRE THEORY THAT FOLLOWS. ── THE TWO CLASSES OF LANGUAGE ───────────────────────────── RECURSIVELY ENUMERABLE (RE), also TURING-RECOGNISABLE or SEMI-DECIDABLE: L is RE if SOME TM M has L(M) = L. On w ∈ L, M accepts (in finite time). On w ∉ L, M rejects OR LOOPS FOREVER. RECURSIVE (R), also DECIDABLE: L is recursive if some TM M has L(M) = L AND M HALTS ON EVERY INPUT. On w ∈ L, M accepts. On w ∉ L, M rejects. NEVER LOOPS. SUCH A MACHINE IS CALLED A DECIDER, and it is what one normally means by "an algorithm". THE CONTAINMENT: RECURSIVE ⊊ RECURSIVELY ENUMERABLE THE PRACTICAL MEANING OF THE DIFFERENCE, which is the point worth grasping before any proof: · A DECIDER always gives an answer. You can wait for it. · A RECOGNISER gives a "yes" if the answer is yes, and MAY GIVE NOTHING AT ALL if the answer is no. IF A RECOGNISER HAS BEEN RUNNING FOR AN HOUR, YOU CANNOT TELL WHETHER THE ANSWER IS "NO" OR WHETHER IT SIMPLY NEEDS ANOTHER MINUTE. That is not ignorance about this particular machine — it is provably impossible to determine in general. ── THE COMPLEMENTATION THEOREM ───────────────────────────── A result that pins the relationship down exactly: IF L AND ITS COMPLEMENT L̄ ARE **BOTH** RECURSIVELY ENUMERABLE, THEN L IS RECURSIVE. THE PROOF IS A DOVETAILING ARGUMENT, and it is short enough to reproduce: Let M₁ recognise L and M₂ recognise L̄. Build a decider D: On input w, RUN M₁ AND M₂ IN PARALLEL — one step of each, alternately. · If M₁ accepts, ACCEPT. · If M₂ accepts, REJECT. EXACTLY ONE OF THEM MUST EVENTUALLY ACCEPT, because w is in either L or L̄. So D always halts, and D decides L. ∎ THE CONTRAPOSITIVE IS THE USEFUL FORM: IF L IS RE BUT **NOT** RECURSIVE, THEN L̄ IS **NOT** RE. This is the standard tool for proving a language is not recursively enumerable, and it is used on the complement of the halting problem. THE PARALLEL SIMULATION IS ESSENTIAL. Running M₁ to completion first would be useless — it might loop, and one would never get to M₂. DOVETAILING — interleaving the two computations step by step — IS THE STANDARD TECHNIQUE FOR RUNNING POSSIBLY-NON-HALTING MACHINES SAFELY, and it recurs throughout computability theory. ── CLOSURE PROPERTIES ────────────────────────────────────── RECURSIVE LANGUAGES are closed under: UNION, INTERSECTION, COMPLEMENT, CONCATENATION, STAR, DIFFERENCE COMPLEMENT IS THE EASY ONE: run the decider and invert its answer. This works ONLY because the decider is guaranteed to halt. RECURSIVELY ENUMERABLE LANGUAGES are closed under: UNION, INTERSECTION, CONCATENATION, STAR BUT **NOT** UNDER COMPLEMENT — which follows directly from the theorem above, since closure under complement would make every RE language recursive. NOTE THE PATTERN ACROSS THE WHOLE SUBJECT: REGULAR closed under complement CONTEXT FREE NOT closed under complement RECURSIVE closed under complement RE NOT closed under complement AND THE REASON IS THE SAME EACH TIME: complementation requires a machine that always gives a definite answer. DFAs and deciders do; PDAs and recognisers do not.

── ACCEPTANCE BY FINAL STATE ─────────────────────────────── The standard convention used above: M accepts w if the computation reaches a state in F. ── ACCEPTANCE BY HALTING ─────────────────────────────────── An alternative: M accepts w if it HALTS at all, regardless of the state. EQUIVALENT IN POWER. Given a final-state machine, build a halting machine that loops deliberately whenever the original would reject; given a halting machine, make every halting configuration accepting. ── ACCEPTANCE FOR TRANSDUCERS ────────────────────────────── When a TM computes a function rather than recognising a language, "acceptance" is replaced by HALTING WITH THE OUTPUT ON THE TAPE — the subject of a later topic. ── WHY THE CONVENTIONS AGREE ─────────────────────────────── Each convention can simulate the others with a small modification, so all define the same class of languages. THIS IS THE SAME ROBUSTNESS ARGUMENT AS FOR THE MACHINE VARIANTS: the model's power does not depend on the details of how acceptance is defined, which is evidence that the notion being captured is real rather than an artefact. ── A WORKED EXAMPLE OF THE DISTINCTION ───────────────────── CONSIDER TWO LANGUAGES: L₁ = { ⟨M, w⟩ : M is a TM that accepts w } THIS IS RECURSIVELY ENUMERABLE. A recogniser simply SIMULATES M on w and accepts if M accepts. If M loops, the simulation loops — which is permitted for a recogniser. IT IS NOT RECURSIVE. This is the halting problem, proved undecidable in a later topic. L₂ = { ⟨M, w, k⟩ : M accepts w WITHIN k STEPS } THIS **IS** RECURSIVE. Simulate M for at most k steps and answer. The bound k guarantees termination. THE DIFFERENCE BETWEEN THEM IS THE PRESENCE OF A BOUND, and that is the general pattern: BOUNDED QUESTIONS ARE DECIDABLE; UNBOUNDED ONES ABOUT MACHINE BEHAVIOUR USUALLY ARE NOT. ── ACCEPTANCE AND THE CHOMSKY HIERARCHY ──────────────────── Completing the correspondence begun in the CFG topic: TYPE 3 REGULAR finite automaton TYPE 2 CONTEXT FREE pushdown automaton TYPE 1 CONTEXT SENSITIVE LINEAR BOUNDED AUTOMATON — a TM whose tape is limited to the length of the input TYPE 0 RECURSIVELY ENUMERABLE TURING MACHINE NOTE WHERE THE RECURSIVE LANGUAGES SIT: BETWEEN TYPE 1 AND TYPE 0, and they are NOT one of Chomsky's four classes. The hierarchy was defined by grammar restrictions, and no natural grammar restriction yields exactly the recursive languages — which is itself a striking fact. The class is defined by a property of MACHINES (always halting) rather than of GRAMMARS. CONTEXT SENSITIVE ⊊ RECURSIVE ⊊ RECURSIVELY ENUMERABLE AND ONE MORE CLASS BEYOND: LANGUAGES THAT ARE NOT EVEN RECURSIVELY ENUMERABLE, such as the complement of the halting problem. THESE ARE NOT RECOGNISED BY ANY MACHINE AT ALL — there is no procedure that even reliably says "yes" when the answer is yes.