Back to the 2022 paper

Module 5: Undecidability

20222m

A recursively enumerable language LL is recursive if:

(i) L′L' is recursively enumerable
(ii) every sequence of moves of TT halts
(iii) Both (i) and (ii)
(iv) None of the above

Worked SolutionAI Assisted

Answer

Correct Option: (i) L′L' is recursively enumerable (equivalently (iii) Both if TT is decider)

Explanation

Theorem (Sipser): RE language LL is recursive (decidable) iff both LL and L‾\overline{L} are RE.

  • If LL is RE and L‾\overline{L} is RE, then dovetail enumerators for LL and L‾\overline{L}; whichever enumerates ww first decides.
  • Formal: LL recursive ⇔ LL RE and L′L' RE.

Option (ii) “every sequence of moves halts” is characterization of decider (always halts), also true for recursive LL but not the standard RE condition. Option (i) is the textbook criterion.

If exam lists (iii) Both (i) and (ii), that is also correct for decider TM. Most keys mark (i) or (iii).

Final Answer

LL recursive iff L′L' is RE → Option (i) (and (iii) Both if inclusive).

Similar questions

Budget AppAndroid App

Pocketly on Android

Log daily food, travel, and hostel expenses instantly. Set monthly spending limits and see where your money goes without complex spreadsheets.