 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2025/ii/paper-3/4f/c/solution

Codex  0 Created 2026-09-24 Updated 2026-09-25

Rename the old halt state

q_{H}

as a nonhalting state

q_{F}

, including every occurrence of

q_{H}

in the original program, and introduce a new halt state

q_{H}

. Attach the following output-flipping routine:

q_{F} q_{0} q_{1} q_{+ 1} q_{+ 0} q_{H} \mapsto ?_{0} (0, q_{0}, q_{1}) \mapsto - (0, q_{+ 1}, q_{+ 1}) \mapsto - (0, q_{+ 0}, q_{+ 0}) \mapsto +_{1} (0, q_{H}) \mapsto +_{0} (0, q_{H}) \mapsto ?_{ε} (0, q_{H}, q_{H}) .

Because the original machine computes a characteristic function, it reaches

q_{F}

with register

0

containing exactly

0

1

. The routine tests that symbol, removes it, and appends its complement. It therefore halts with

1 - χ_{X} (w) = χ_{B ∖ X} (w)

 New to topics? Read the docs here!