A program P is given a description of a Turing machine M and input w. When M accepts w, P always halts and outputs 'yes.' When M rejects or loops on w, P sometimes outputs 'no' and sometimes runs forever. Is P a decider for the acceptance problem?
AYes — P always gives the correct answer when M accepts, so it correctly recognizes the language
BNo — a decider must halt on ALL inputs and produce a definitive yes or no; P fails this requirement for inputs where M rejects or loops
CYes — P never outputs a wrong answer, which is sufficient for a decider
DNo — the acceptance problem requires checking infinitely many inputs simultaneously
P is a recognizer (semi-decider), not a decider. The critical requirement for a decider is that it must halt on every input — including those where the answer is 'no' — and output a definitive accept or reject. When P loops on some inputs, you can never distinguish 'this machine will eventually halt and reject' from 'this machine will loop forever.' A looping machine gives no information. This is exactly the distinction between recognizable (may loop on non-members) and decidable (always halts with yes or no).
Question 2 Multiple Choice
All regular and context-free languages are decidable. Which is the key reason that gives these language classes decidability guarantees that do not extend to all languages?
ARegular and CFL grammars are simple enough that TMs can process them without using the tape
BSimulating a DFA on finite input always terminates; the CYK algorithm for CFLs always terminates — both provide guaranteed yes/no answers in finite time
CThese language classes contain only finite strings, so all decisions terminate
DAll language classes are decidable given sufficient computing time
Decidability requires that the deciding TM always halt. For regular languages, simulating a DFA trivially terminates after reading |w| steps and reaches accept or reject. For CFLs, the CYK algorithm is a terminating dynamic programming method that produces a definitive yes or no. Problems that become undecidable — like 'does TM M accept input w?' — lack this guarantee: no algorithm can always terminate with the correct answer for all instances, not from lack of cleverness but by provable impossibility.
Question 3 True / False
If a language L is decidable, then its complement (all strings NOT in L) is also decidable.
TTrue
FFalse
Answer: True
If a TM M decides L, swapping its accept and reject states produces a TM that decides the complement. Since M always halts and gives accept or reject, the swapped machine also always halts — accepting exactly the strings not in L and rejecting exactly the strings in L. This symmetry holds for decidable languages but NOT for merely recognizable ones: the complement of a recognizable language need not be recognizable, which is a key asymmetry between the two classes.
Question 4 True / False
A Turing machine that runs forever on a specific input has encountered an undecidable problem.
TTrue
FFalse
Answer: False
A looping TM on a specific input tells you nothing about whether the underlying problem is decidable. That particular TM may be poorly designed, or it may be a recognizer that loops on non-members by design. Undecidability is a property of languages (problems), not of individual machines: a problem is undecidable if NO Turing machine (however clever) can decide it. A single looping machine leaves open the possibility that a different, better TM could decide the same problem. Proving undecidability requires showing no TM whatsoever can do it — typically via reduction from the halting problem.
Question 5 Short Answer
Why is the distinction between 'recognizable' and 'decidable' practically important, and not merely a theoretical curiosity?
Think about your answer, then reveal below.
Model answer: Because a recognizer gives asymmetric information: a 'yes' answer arrives in finite time, but a 'no' answer may never arrive — the machine loops forever, and you cannot distinguish 'still computing' from 'will loop forever.' A decider guarantees an answer in finite time for every input. For recognizable-but-undecidable problems (like the halting problem), any program that tries to decide them will either give wrong answers on some inputs or fail to terminate on others — and no engineering improvement can fix this. It is a provable limit on what algorithms can accomplish.
This matters practically whenever you need a guaranteed terminating procedure: program verification, type checking, and many other software engineering problems touch decidability limits. Understanding the distinction prevents wasted effort searching for algorithms that provably cannot exist.