Self-Assessment Quiz: Computability and the Halting Problem

Twenty questions to check your understanding. Answer before opening the key. Aim for 16+. Throughout, "program" means "Turing machine" (the Church–Turing thesis lets us use the words interchangeably).

Question 1

A Turing machine is required to have a finite set of states and a finite transition function, but one component is unbounded. Which?

A) the input alphabet $\Sigma$ B) the tape C) the set of accept states D) the number of directions the head can move

Question 2

On a given input, a Turing machine has exactly how many possible fates?

A) one (it always accepts) B) two (accept or reject) C) three (accept, reject, or loop forever) D) infinitely many

Question 3

The single capability a Turing machine has that a DFA (Chapter 35) lacks, and which makes "loop forever" possible, is:

A) a larger alphabet B) a writable, unbounded tape that the head can revisit C) more than one accept state D) nondeterminism

Question 4

The Church–Turing thesis is best described as:

A) a theorem proved by Turing in 1936 B) a definition of "Turing machine" C) an evidence-backed claim equating "computable by an algorithm" with "computable by a Turing machine" D) a conjecture that has since been disproved

Question 5 (True/False, justify)

True or false: Because the lambda calculus, general recursive functions, and Turing machines were all proved to compute the same functions, the Church–Turing thesis is therefore proved. Justify in one sentence.

Question 6

The single difference between a decider and a recognizer for a language $L$ is:

A) a decider accepts members of $L$; a recognizer does not B) a decider may loop on members; a recognizer may not C) a decider halts on every input; a recognizer may loop forever on non-members D) there is no difference

Question 7

"Run program $P$ on input $x$ and accept if it stops" is:

A) a decider for the halting problem B) a recognizer for the halting problem, but not a decider C) neither a recognizer nor a decider D) a decider for the complement of the halting problem

Question 8

Which containment is correct?

A) recognizable $\subsetneq$ decidable B) decidable $\subsetneq$ recognizable C) decidable $=$ recognizable D) decidable and recognizable are disjoint

Question 9

In the halting-problem proof, the single assumption made for contradiction is:

A) that programs are uncountable B) that a decider $H$ for the halting problem exists C) that the program $D$ halts on all inputs D) that the tape is finite

Question 10

The contrarian program $D$ in the proof is defined to:

A) always halt B) always loop C) run $H(P,P)$ and then do the opposite of what $H$ predicts D) simulate $P$ on $x$ step by step

Question 11

The contradiction that ends the halting proof is the statement:

A) "$H$ is both a decider and a recognizer" B) "$D$ halts on $D$ if and only if $D$ does not halt on $D$" C) "programs are both countable and uncountable" D) "$D$ accepts every input and rejects every input"

Question 12 (True/False, justify)

True or false: The procedure "simulate $P$ on $x$ for $10^6$ steps; if it halted say 'halts,' else say 'loops'" decides the halting problem because it always terminates. Justify in one sentence.

Question 13

"$A \le B$" (problem $A$ reduces to problem $B$) means:

A) $A$ is at least as hard as $B$ B) $B$ is at least as hard as $A$ — a solver for $B$ would solve $A$ C) $A$ and $B$ are equally hard, always D) $A$ is decidable and $B$ is not

Question 14

To prove a new problem $B$ is undecidable by reduction, you must show:

A) $B \le \mathrm{HALT}$ B) $\mathrm{HALT} \le B$ C) $B \le B$ D) $B$ is recognizable

Question 15

In the reduction proving the empty-acceptance problem ($\mathrm{EMPTY}$) undecidable, the constructed program $P'$ is built so that:

A) $P'$ halts iff $P$ loops B) $P'$ accepts nothing iff $P$ loops on $x$ C) $P'$ accepts everything iff $P$ loops on $x$ D) $P'$ is identical to $P$

Question 16

Why is it essential that building the gadget $P'$ does not require running $P$?

A) running $P$ would be too slow B) if building $P'$ required running $P$, the reduction itself might never halt and so would not be an algorithm C) $P$ might modify $P'$ D) it isn't essential; running $P$ is fine

Question 17 (True/False, justify)

True or false: The problem "does program $P$ halt on input $x$ within 10,000 steps?" is undecidable, just like the unbounded halting problem. Justify in one sentence.

Question 18

A static analyzer that is sound but incomplete has which property?

A) every bug it reports is real, but it misses some real bugs B) it reports every real bug, but some reports are false alarms C) it reports exactly the real bugs and nothing else D) it never reports anything

Question 19

Undecidability forces a behavioral program-analysis tool to give up at least one of soundness and completeness because:

A) hardware is too slow B) a tool that was both sound and complete for a nontrivial behavioral property would decide an undecidable problem C) programmers prefer false alarms D) the Church–Turing thesis forbids it

Question 20 (Short answer)

Name two distinct strategies real tools use to cope with an undecidable question, with a one-word example of each (drawn from §36.6).

Answer Key

Topics to review by question