Turing Machines & Undecidability

Recursive and Recursively Enumerable Languages

Recursive Enumerable (RE) or Type-0 Language

A language is recursively enumerable (RE) or Turing-recognisable if there exists a Turing machine that accepts every string in the language. For any string in the language the machine eventually enters an accepting (final) state; for strings not in the language the machine may either reject or run forever (loop). RE languages are exactly the languages generated by Type-0 grammars.

Recursive Language (REC)

A language is recursive (also called Turing-decidable) if there exists a Turing machine that halts on every input and correctly decides membership: it accepts when the input is in the language and rejects when it is not. Every recursive language is recursively enumerable, but the converse need not hold.

Example: L = {aⁿbⁿcⁿ | n ≥ 1} is recursive because a Turing machine can be constructed to check equal numbers of a, b and c by suitable marking and counting; the machine always halts with the correct answer.

The containment relationship is: REC ⊆ RE. (REC is a proper subset of RE in general.)

Closure Properties of Recursive Languages

• Union: If L₁ and L₂ are recursive, then L₁ ∪ L₂ is recursive because we can run the deciders for L₁ and L₂ in sequence or in parallel and always halt with the correct yes/no answer.
• Concatenation: If L₁ and L₂ are recursive then L₁·L₂ is recursive, since a decider can enumerate splits of the input and run the deciders for L₁ and L₂ for each split; because both deciders always halt this procedure always halts.
• Kleene closure: If L is recursive, then L* is recursive. A decider can test whether the input can be partitioned into a finite sequence of strings each in L by trying all possible partitionings; finiteness of the search is ensured because each test uses deciders that halt.
• Intersection and complement: Recursive languages are closed under intersection and complement. If L is recursive then Σ* \ L is recursive, and if L₁ and L₂ are recursive then L₁ ∩ L₂ is recursive.

Example for concatenation: L1 = {aⁿbⁿcⁿ | n ≥ 0} L2 = {d^me^mf^m | m ≥ 0} L3 = L1·L2 = { aⁿbⁿcⁿd^me^mf^m | n ≥ 0, m ≥ 0 } is recursive.

Note: As opposed to REC languages, RE languages are not necessarily closed under complement; the complement of an RE language need not be RE.

Question 1: Which of the following statements is/are FALSE?

1.For every non-deterministic TM, there exists an equivalent deterministic TM.
2.Turing recognizable languages are closed under union and complementation.
3.Turing decidable languages are closed under intersection and complementation.
4.Turing recognizable languages are closed under union and intersection.

A.1 and 4
B.1 and 3
C.2
D.3

Solution:

Statement 1 is true: every non-deterministic Turing machine can be simulated by a deterministic Turing machine (non-determinism does not add to the class of languages recognised by Turing machines).

Statement 2 is false: Turing-recognisable (RE) languages are closed under union but not closed under complementation in general.

Statement 3 is true: Turing-decidable (recursive) languages are closed under intersection and complementation.

Statement 4 is true: Turing-recognisable languages are closed under union and intersection.

Question 2 : Let L be a language and L' be its complement. Which one of the following is NOT a viable possibility?

A.Neither L nor L' is RE.
B.One of L and L' is RE but not recursive; the other is not RE.
C.Both L and L' are RE but not recursive.
D.Both L and L' are recursive.

Solution:

Option A: viable. It is possible that neither L nor L' is RE.

Option B: viable. One may be RE (but not recursive) while the other is not RE; RE is not closed under complementation.

Option C: not viable. If both L and L' were RE then both would be recursive (because a language whose complement is also RE is decidable), so they cannot be both RE but not recursive.

Option D: viable. If L is recursive then so is L'.

Thus option C is not a viable possibility.

Question 3: Let L1 be a recursive language, and let L2 be a recursively enumerable but not a recursive language. Which one of the following is TRUE?

A.L1′ is recursive and L2′ is recursively enumerable
B.L1′ is recursive and L2′ is not recursively enumerable
C.L1′ and L2′ are recursively enumerable
D.L1′ is recursively enumerable and L2′ is recursive

Solution:

L1 is recursive, so L1′ is recursive (recursive languages are closed under complement). L2 is RE but not recursive; since RE need not be closed under complement, L2′ need not be RE (indeed for many standard RE but not recursive languages, the complement is not RE). Therefore option B is correct.

Turing Machine

Alan Turing introduced the Turing machine model in 1936. The Turing machine is a fundamental model of computation that captures the intuitive notion of algorithmic computation and recognises recursively enumerable languages.

A (single-tape) Turing machine can be described as the 7-tuple (Q, Σ, Γ, δ, q₀, B, F), where:

• Q is a finite set of states.
• Σ is the input alphabet (not containing the blank symbol).
• Γ is the tape alphabet, Σ ⊆ Γ, and Γ contains a special blank symbol.
• δ is the transition function δ : Q × Γ → Q × Γ × {L, R} for a deterministic TM.
• q₀ ∈ Q is the start state.
• B ∈ Γ is the blank symbol filling all but finitely many cells initially.
• F ⊆ Q is the set of accepting (final) states.

Example: A Turing machine for L = {0ⁿ1ⁿ | n ≥ 1}

• Q = {q0, q1, q2, q3} where q0 is the initial state.
• Γ = {0, 1, X, Y, B} where B represents blank; X and Y are used as marks.
• Σ = {0, 1}.
• F = {q3} (q3 is the accepting state).

The transition function δ for this machine is shown in the table below.

Illustration of operation

We trace the machine on the input 0011. Initially the head is on the leftmost symbol and the machine is in state q0.

First move: δ(q0, 0) = (q1, X, R). The machine writes X in place of the first 0, moves right and goes to state q1.

Next moves: δ(q1, 0) = (q1, 0, R) - the machine scans right over any 0s without changing them.

When it sees 1: δ(q1, 1) = (q2, Y, L). It replaces that 1 by Y, moves left and goes to state q2.

Continuing similarly, the machine will match each 0 with a corresponding 1, mark them with X and Y, and finally reach state q3 with the head on a blank. The move δ(q3, B) = halt causes acceptance.

Remarks

• In a non-deterministic Turing machine there may be multiple possible moves for a given state and tape symbol, but non-determinism does not increase the class of languages recognised: every non-deterministic TM can be simulated by a deterministic TM.
• Multi-tape Turing machines have several tapes and heads; they do not recognise more languages than single-tape machines because every multi-tape TM can be simulated by a single-tape TM.

Question: A single tape Turing Machine M has two states q0 and q1, of which q0 is the starting state. The tape alphabet of M is {0, 1, B} and its input alphabet is {0, 1}. The symbol B is the blank symbol used to indicate end of an input string. The transition function of M is described in the following table.

The table is interpreted as illustrated below. The entry (q1, 1, R) in row q0 and column 1 signifies that if M is in state q0 and reads 1 on the current tape square, then it writes 1 on the same tape square, moves its tape head one position to the right and transitions to state q1. Which of the following statements is true about M?

1. M does not halt on any string in (0 + 1)+
2. M does not halt on any string in (00 + 1)*
3. M halts on all string ending in a 0
4. M halts on all string ending in a 1

Solution:

Consider the input string 1. Initially the machine is in q0 and the head is on the single symbol 1.

Using δ(q0, 1) = (q1, 1, R), the machine moves to state q1 and the head moves right.

Now the head reads the blank B. Using δ(q1, B) = (q0, B, L), the machine moves back to state q0 and the head moves left.

The machine repeats the same moves and never halts on input 1.

Option D claims the machine halts on all strings ending with 1, but we have found a counterexample (the string 1), so D is incorrect.

Consider the input string 0. The machine similarly cycles and does not halt.

Hence option C is also incorrect.

Option B asserts the machine does not halt on any string in (00 + 1)*, but the empty string is in (00 + 1)* and the machine halts on the empty input because δ(q0, B) = halt.

Therefore option A is the only correct statement: M does not halt on any non-empty string in (0 + 1)+.

Undecidability and Reducibility

Decidable Problems

A decision problem (language) is decidable if there exists a Turing machine that always halts and answers yes or no correctly for every input. Decidable problems have algorithms that terminate for every input.

Examples:

• Equivalence of two regular languages: Given two regular languages (for example, two DFAs), there is an algorithm to decide whether they denote the same language.
• Finiteness of a regular language: Given a regular language, one can decide whether it contains only finitely many strings.
• Emptiness of a context-free language: Given a context-free grammar, there is a procedure to decide whether the language generated is empty.

Undecidable Problems

A problem is undecidable if no Turing machine can always halt and correctly decide the problem for every input. Undecidable problems have no algorithm that terminates on all inputs with the correct yes/no answer.

Examples:

• Ambiguity of context-free grammars: Given a context-free grammar G, there is no general algorithm that always halts and determines whether G is ambiguous.
• Equivalence of two context-free languages: Given two context-free grammars, there is no algorithm that always decides whether they generate the same language.
• Universality (completeness) of a CFG: Given a CFG G and alphabet Σ, determining whether L(G) = Σ* is undecidable.
• Regularity of CFL, CSL, REC: Given a description of a CFL, CSL or a recursively enumerable language, deciding whether the language is regular is undecidable in general.

Two classical undecidable problems are the Halting Problem for Turing machines and the Post Correspondence Problem (PCP).

Semi-decidable Problems

A problem is semi-decidable (or semi-decidable/partially decidable) if there is a Turing machine that halts and accepts precisely the yes-instances, but for no-instances it may reject or loop forever. Semi-decidable problems correspond to RE languages.

Rice's Theorem

Rice's Theorem: Every non-trivial semantic property of recursively enumerable languages is undecidable. Informally, any non-trivial question about the language recognised by a Turing machine (as opposed to its syntactic description) is undecidable. For example, given a Turing machine M, asking whether L(M) has a particular non-trivial property is undecidable.

Reducibility and Undecidability

We use reducibility to transfer decidability or undecidability from one language to another.

Language A is reducible to language B (written A ≤ B) if there exists a computable function f such that for every string w:

w ∈ A <=> f(w) ∈ B

Theorems:

• If A ≤ B and B is decidable then A is decidable.
• If A ≤ B and A is undecidable then B is undecidable.

Question: Which of the following is/are undecidable?

1. G is a CFG. Is L(G) = ∅ ?
2. G is a CFG. Is L(G) = Σ* ?
3. M is a Turing machine. Is L(M) regular?
4. A is a DFA and N is an NFA. Is L(A) = L(N) ?

A. 3 only
B. 3 and 4 only
C. 1, 2 and 3 only
D. 2 and 3 only

Explanation:

• Option 1: Emptiness for a CFG (L(G) = ∅) is decidable.
• Option 2: Universality for a CFG (L(G) = Σ*) is undecidable.
• Option 3: Given a Turing machine M, determining whether L(M) is regular is undecidable.
• Option 4: Equivalence of a DFA and an NFA is decidable (convert the NFA to a DFA or use standard algorithms).

Hence options 2 and 3 are undecidable; answer D is correct.

Question: Which of the following problems are decidable?

1. Does a given program ever produce an output?
2. If L is context free language then L' is also context free?
3. If L is regular language then L' is also regular?
4. If L is recursive language then L' is also recursive?

A. 1,2,3,4
B. 1,2
C. 2,3,4
D. 3,4

Explanation:

• Regular languages are closed under complement, so option 3 is decidable.
• Recursive languages are closed under complement, so option 4 is decidable.
• Context-free languages are not closed under complement in general, so option 2 is not a decidable assertion (the property "If L is CFL then L' is CFL" is false in general).
• Whether a given program ever produces an output is in general undecidable (this relates to the Halting Problem), so option 1 is undecidable.

Therefore options 3 and 4 are decidable; answer D is correct.

Question: Consider three decision problems P1, P2 and P3. It is known that P1 is decidable and P2 is undecidable. Which one of the following is TRUE?

A. P3 is undecidable if P2 is reducible to P3
B. P3 is decidable if P3 is reducible to P2's complement
C. P3 is undecidable if P3 is reducible to P2
D. P3 is decidable if P1 is reducible to P3

Explanation:

• Option A: If P2 ≤ P3 and P2 is undecidable, then by the reducibility theorem P3 must be undecidable. So option A is correct.
• Option C: P3 ≤ P2 does not imply P3 is undecidable; reducibility in that direction would imply that undecidability of P3 would imply undecidability of P2, but P2 is already known to be undecidable-this does not force P3 to be undecidable.
• Option D: P1 ≤ P3 and known decidability of P1 does not imply decidability of P3. Reducibility of a decidable problem to another problem gives no conclusion about the latter.
• Option B: P3 ≤ P2' does not guarantee decidability of P3 even if P2' were undecidable; reducibility to an undecidable problem (or its complement) does not establish decidability.

Thus, option A is the correct choice.