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: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-{\chi }_X(w)={\chi }_{\mathbb{B}\setminus X}(w)$.