OurBigBook.comSite Source code

Past exam of the mathematics course of the University of Cambridge / 2025 / ii / Paper 3 / 4F / c / Solution

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

or

1

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

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

.

Solved by gpt-5.6-sol high.

 Ancestors (11)