Each worksheet prints cleanly on A4 or Letter. Answer keys are on a separate page.

The Lumenary · Advanced undergraduate

Computability

Name: ______________________

Date: ______________________

You will learn to

Design simple Turing machines, trace their computations and explain why the model is believed to capture every algorithm (the Church–Turing thesis)
Define decidable and recursively enumerable sets, and prove that a set is decidable if and only if both it and its complement are recursively enumerable
Prove that the halting problem is undecidable by a diagonal argument, and that most functions $\N \to \N$ are not computable
Use many-one reductions to prove undecidability, and prove Rice's theorem
Recognise undecidability in other parts of mathematics, from Diophantine equations to groups and tilings

1.
The one-state binary incrementer of the lesson starts on the least significant bit of $10111$ (twenty-three). How many steps does it take before it halts?
2.
A Turing machine has $3$ states and the two symbols $0, 1$ . Each of its $3 \times 2 = 6$ table entries chooses a symbol to write, a direction (L or R) and a next state, which is one of the $3$ states or halt. How many different tables are there?
3.
Which of these sets are recursively enumerable? (Select all that apply.)
- A. $K = \{e \mid \varphi_e(e)\!\downarrow\}$
- B. $\overline{K} = \{e \mid \varphi_e(e)\!\uparrow\}$
- C. $\{e \mid \varphi_e(0) = 7\}$
- D. $\{e \mid M_e \text{ has at most } 10 \text{ states}\}$
- E. $\mathrm{Tot} = \{e \mid \varphi_e \text{ is total}\}$
4.
In the proof that $K$ is undecidable we assumed a machine computing the total function $h$ . Suppose instead we only had a semi-decider $s$ for $K$ : it halts with output $1$ when $\varphi_e(e)\!\downarrow$ and runs forever otherwise. Build $D$ as before (on input $x$ : run $s(x)$ ; if it outputs $1$ , loop forever; otherwise halt). What happens?
- A.No contradiction: $D$ loops on every input, so $\varphi_d(d)\!\uparrow$ , which is consistent.
- B.The same contradiction arises, so $K$ is not even r.e.
- C. $D$ is not a Turing machine, because it uses $s$ as a subroutine.
- D. $D$ halts on its own index, so $d \in K$ .
5.
You want to prove that a new set $B$ is undecidable, using the undecidability of $K$ . Which do you need to show?
- A. $K \le_m B$ : a computable $f$ with $e \in K \iff f(e) \in B$ .
- B. $B \le_m K$ : a computable $f$ with $x \in B \iff f(x) \in K$ .
- C. $K \subseteq B$ .
- D. $B$ is infinite and not equal to $\N$ .
6.
For which of these properties of an index $e$ does Rice's theorem show that the set of $e$ with the property is undecidable? (Select all that apply.)
- A. $\varphi_e$ is total.
- B. $\varphi_e(3) = 3$ .
- C. $M_e$ has an even number of states.
- D. $M_e$ halts on input $0$ within $100$ steps.
- E. $\varphi_e$ is a partial computable function.
7.
In Mathlib, c.eval n is the (partial) result of running program c : Nat.Partrec.Code on input n, and (c.eval n).Dom says that it halts. Which Lean statement says that halting on input n is undecidable?
- A.¬ ComputablePred fun c : Code => (c.eval n).Dom
- B.¬ ∃ c : Code, (c.eval n).Dom
- C.¬ REPred fun c : Code => (c.eval n).Dom
- D.∀ c : Code, ¬ Decidable ((c.eval n).Dom)
8.
Write run(machine, max_steps) that simulates a two-symbol Turing machine started in state 0 on a blank tape. machine is a dict mapping (state, symbol) to (write, move, next_state), with move in (-1, 1) and next_state equal to None for halt. Return ("halt", steps, ones) if it halts within max_steps steps (counting the halting step) and ("running", max_steps, ones) otherwise, where ones is the number of 1s on the tape at that moment.
Computational — Practice
9.
We want to prove for all $n \ge 0$ that the incrementer, started on the binary expansion of $n$ with the head on the last bit, halts with $n + 1$ on the tape after $t(n) + 1$ steps, where $t(n)$ is the number of trailing $1$ s. Which induction works?
- A.Strong induction on $n$ : if $n$ is even, one step suffices; if $n = 2m + 1$ , the first step writes $0$ and moves left, leaving the machine in exactly the starting situation for $m$ .
- B.Ordinary induction from $n$ to $n + 1$ , using that the machine on $n + 1$ starts where the machine on $n$ stopped.
- C.No induction is needed: checking all $n < 256$ is enough because larger numbers behave the same way.
- D.Induction on the number of states.

Answer key — Computability

1.
The machine takes $t + 1$ steps, where $t$ is the number of trailing $1$ s. Here $t = 3$ : three steps turn $10111$ into $10000$ with the head on the $0$ , and a fourth step writes $1$ and halts, giving $11000$ (twenty-four). Answer: $4$ .
2.
Each entry has $2$ (symbol) $\times 2$ (direction) $\times 4$ (three states or halt) $= 16$ options, and there are $6$ entries, so there are $16^6 = 2^{24} = 16\,777\,216$ tables. For two states the same count gives $12^4 = 20\,736$ , the number the busy-beaver experiment classifies. Exhaustive search grows very fast — and the undecidability of halting says that for large enough $n$ no finite set of certificate methods can settle all machines.
3.
$K$ , $\{e \mid \varphi_e(0) = 7\}$ and $\{e \mid M_e \text{ has at most } 10 \text{ states}\}$ are r.e. (the last is decidable). $\overline{K}$ is not r.e. (Corollary 5). $\mathrm{Tot}$ is not r.e.: given $e$ , let $M_{f(e)}$ on input $n$ simulate $M_e$ on $e$ for $n$ steps, loop forever if that simulation has halted, and halt otherwise. Then $\varphi_{f(e)}$ is total iff $e \in \overline{K}$ , so $\overline{K} \le_m \mathrm{Tot}$ and $\mathrm{Tot}$ is not r.e. by Lemma 7.
4.
With a semi-decider, $D$ never reaches its "halt" branch: on $x \in K$ it loops by design, and on $x \notin K$ it waits forever for $s$ . So $D$ computes the nowhere-defined function, $\varphi_d(d)\!\uparrow$ , and the case analysis gives no contradiction. The original proof used totality of $h$ exactly once — in the step "if $h(x) = 0$ , halt". This is why $K$ is r.e. but not decidable.
5.
Show $K \le_m B$ . By Lemma 7, if $B$ were decidable then $K$ would be decidable, contradicting Theorem 2. Reductions go from the known hard problem to the new one.
6.
Rice's theorem applies to the first two: they depend only on $\varphi_e$ and are non-trivial. "Even number of states" and "halts within 100 steps" are not semantic (and are decidable). "Partial computable" is semantic but trivial. Rice's theorem is a statement about functions computed, never about program text or running time.
7.
¬ ComputablePred fun c : Code => (c.eval n).Dom is Mathlib's halting theorem. Option b is false, option c is false (the halting set is r.e.), and option d confuses the logical notion of a decidable proposition (true classically for every proposition) with the computational notion of a decidable predicate.

def run(machine, max_steps):
    tape = {}
    pos, state = 0, 0
    for steps in range(1, max_steps + 1):
        write, move, state = machine[(state, tape.get(pos, 0))]
        tape[pos] = write
        pos += move
        if state is None:
            return ("halt", steps, sum(tape.values()))
    return ("running", max_steps, sum(tape.values()))

Note the asymmetry: "halt" is a proof that the machine halts, while "running" proves nothing about the future. The busy beaver bb2 is still running after 5 steps and halts at step 6.

9.
Strong induction on $n$ . If the last bit is $0$ (or $n = 0$ , a blank), the machine writes $1$ and halts after $1 = t(n) + 1$ step, and the tape spells $n + 1$ . If $n = 2m + 1$ , the first step writes $0$ and moves left; now the head is on the last bit of $m$ in state carry, so by the induction hypothesis the machine halts after $t(m) + 1$ further steps with $m + 1$ written to the left of the $0$ . The tape spells $2(m + 1) + 0 = n + 1$ , and the step count is $1 + t(m) + 1 = t(n) + 1$ because $t(2m + 1) = t(m) + 1$ .