Questions: Decidable and Semi-Decidable Languages

Question 1

What does it mean to say the halting problem is semi-decidable?

• A. There exists a Turing machine that always halts and correctly answers 'yes' or 'no' for every input
• B. There exists a Turing machine that halts and accepts whenever a program halts on its input, but may run forever when the program does not halt
• C. The halting problem can be decided in exponential time but not polynomial time
• D. The halting problem is almost decidable — a small fraction of inputs cannot be determined

Answer: (B)

Semi-decidable means there is a TM that accepts every member of the language (here: every (program, input) pair where the program halts) but may run forever on non-members. For the halting problem: simulate the given program. If it halts, output 'yes' and halt. If it runs forever, your simulator also runs forever — never producing a 'no.' You can confirm halting but cannot confirm non-halting. Option A describes decidability. Option C confuses decidability with computational complexity. Option D misrepresents the gap as quantitative — it is absolute.

Question 2

A language L is recursively enumerable (RE). Its complement L̄ is also recursively enumerable. What can we conclude?

• A. L is undecidable, because two RE machines cannot decide a language
• B. L is decidable, because we can run both machines in parallel and one will always halt with the correct answer
• C. L is in co-RE but not necessarily in RE
• D. Nothing — knowing both L and L̄ are RE tells us only that L is semidecidable in both directions

Answer: (B)

If both L and L̄ are RE, dovetail two TMs: M₁ that semi-decides L and M₂ that semi-decides L̄. For any input x, either x ∈ L or x ∈ L̄ — one of the two machines will eventually halt and accept. Run both in parallel (alternating steps); whichever accepts first gives the decision. This constructs a TM that always halts with the correct yes/no answer — a decider. Decidability equals RE ∩ co-RE, and having both L ∈ RE and L̄ ∈ RE (which means L ∈ co-RE) is exactly that intersection.

Question 3

If a language L is decidable, then its complement L̄ is also decidable.

• T. True
• F. False

Answer: True

If TM M decides L (always halts, accepts on L-members, rejects on non-members), construct M̄ by swapping the accept and reject states. M̄ accepts exactly the inputs M rejects — which are the non-members of L, i.e., the members of L̄. M̄ always halts (because M always halts) and correctly decides L̄. Decidability is closed under complementation. This contrasts with semi-decidability: the halting problem is RE but its complement (non-halting) is not RE, so RE is not closed under complementation.

Question 4

A semi-decidable language can be made decidable by adding a timeout: if the Turing machine does not halt within some fixed number of steps, output 'no.'

• T. True
• F. False

Answer: False

This is the most tempting misconception about semi-decidability. Adding a timeout creates a TM that always halts, but it no longer correctly decides the language — it incorrectly rejects inputs that would have been accepted after more steps. The gap between semi-decidable and decidable is absolute: no finite timeout can serve as a correct 'no' witness, because for any timeout value T, there are programs that halt after T+1 steps. You cannot know in advance how long to wait, and no bound works for all inputs simultaneously.

Question 5

Explain why the gap between semi-decidable and decidable is 'absolute' — why can't a semi-decision procedure be converted into a decision procedure by limiting computation time?

Model answer: A semi-decision procedure has an asymmetry: it can produce 'yes' witnesses (accepting) but never produces 'no' witnesses — it just runs forever on non-members. To convert it to a decider, you'd need a finite time after which you can safely output 'no.' But for the halting problem, programs can take arbitrarily long to halt: for any timeout T you choose, there exist programs that halt on step T+1. Stopping at T and outputting 'no' would incorrectly reject those programs. There is no computable function that bounds the runtime of all halting programs, so no timeout is correct for all inputs. The gap is absolute because 'may run forever on non-members' cannot be made finite by a computable bound.

The reason this fails is that the set of programs that halt within T steps grows as T grows, but is never the complete set of halting programs. Deciding membership in the halting problem would require knowing, for an arbitrary program, whether it eventually halts — which is exactly the undecidable question you started with. Any timeout-based approach simply relocates the problem rather than solving it.