Questions: Recursive Languages: The Decidable Languages

Question 1

A Turing machine M processes every possible input string and either accepts or rejects it — always halting. Which statement about the language L = {w | M accepts w} is correct?

• A. L is recursively enumerable but not necessarily recursive, because a Turing machine is involved
• B. L is recursive (decidable), because M is a decider — it always halts and gives the correct yes/no answer
• C. L is recursive only if it is also context-free or regular
• D. L is recursive only if M halts within polynomial time on every input

Answer: (B)

The definition of a recursive (decidable) language is exactly: there exists a Turing machine that always halts and correctly accepts members and rejects non-members. M described here is precisely a decider. The distinction from RE is the 'always halts' condition — RE only requires accepting members, allowing the machine to loop on non-members. Option A is the classic confusion: being recognized by a TM defines RE; being *decided* by a TM (always halting) defines recursive.

Question 2

Which of the following correctly describes the relationship between recursive and recursively enumerable (RE) languages?

• A. Every recursive language is RE, but not every RE language is recursive — RE is the larger class
• B. Every RE language is recursive, because any recognizer can be modified to always halt
• C. Recursive and RE languages are disjoint — no language belongs to both classes
• D. RE languages are a proper subset of recursive languages, because RE is more restrictive

Answer: (A)

Recursive ⊂ RE: any decider is also a recognizer (it halts and accepts members, halts and rejects non-members — in particular, it accepts all members). But RE ⊄ Recursive: the halting problem is RE (you can confirm halting by simulation) but not recursive (no TM can decide halting in general). Option B is the critical misconception — you cannot simply modify a recognizer to always halt without solving the halting problem. The looping behavior on non-members is not a bug to be fixed; it is fundamental to languages that are RE but not decidable.

Question 3

If language L is recursive (decidable), then its complement L̄ (all strings not in L) is also recursive.

• T. True
• F. False

Answer: True

True. Given a decider M for L, construct M' by swapping accept and reject states: wherever M accepted, M' rejects; wherever M rejected, M' accepts. M' is still a decider (always halts) and accepts exactly the strings not in L. This symmetry — that decidable languages are closed under complementation — is unique to the recursive class. RE languages are NOT generally closed under complementation: the halting problem is RE, but its complement (all (M, w) where M does not halt on w) is not RE. A language is recursive if and only if both it and its complement are RE.

Question 4

A language is recursive if and only if there exists a Turing machine that eventually accepts most string in the language, even if it runs forever on strings not in the language.

• T. True
• F. False

Answer: False

False. That is the definition of recursively enumerable (RE), not recursive. Recursive (decidable) requires a TM that always halts on ALL inputs — both members and non-members — giving an explicit accept or reject. The condition 'runs forever on non-members' is precisely what distinguishes RE from recursive. RE is a weaker guarantee: you can confirm membership but never confirm non-membership by waiting. Recursive provides symmetric, finite-time answers for both.

Question 5

The class of recursive languages is described as the class of 'algorithmically solvable' problems. Why does the 'always halts' condition capture what it means to have an algorithm?

Model answer: An algorithm, in the practical sense, is a step-by-step procedure guaranteed to terminate with a definitive answer. If a procedure might run forever, it fails as an algorithm: you would never know whether to keep waiting or conclude you won't get an answer. The 'always halts' condition formalizes this: a decider for L terminates on every input and outputs yes or no in finite time. This matches the informal notion of solving a problem — for any problem instance, you can run the procedure and receive a definitive answer. A recognizer that loops on non-members cannot serve as an algorithm for deciding membership, because infinite running time is ambiguous: the machine might be about to accept, or might loop forever.

This is the Church-Turing thesis applied to decision problems: the intuitive notion of 'there exists an algorithm to solve this' corresponds precisely to 'there exists a Turing machine decider.' The thesis is not provable (it connects an informal concept to a formal one) but is universally accepted based on the equivalence of all known models of computation. When complexity theory later restricts to polynomial-time deciders (class P), it is asking not just whether an algorithm exists, but whether an *efficient* one does — a refinement within the recursive class.