Diagonalization and the Halting Problem

Build a deterministic one-tape machine $R$ that, on input $z$, first parses $z$ as a candidate pair $⟨x,y⟩$. If the pair parse fails, it rejects. It next runs the decider from [L4] on $x$; if $x$ is not a well-formed machine code, it rejects. If $x$ is valid, it uses [L2] to recover the coded machine $M=(m,s,n,\tau )$. It then parses $y$ as a candidate word code $c(\mathrm{bin}(\mathrm{\ell }))c(\mathrm{bin}(a_1))\cdots c(\mathrm{bin}(a_{\mathrm{\ell }}))$, rejects if that parse fails, and also rejects if some recovered symbol $a_i$ lies outside the input alphabet ${\mathrm{\Sigma }}_s=\{1,\dots ,s\}$. From the recovered word $w=a_1\cdots a_{\mathrm{\ell }}$, the machine writes the canonical initial configuration code of $M$ on input $w$.

The machine $R$ now repeatedly invokes the one-step interpreter from [L3] on the pair consisting of the recovered code $x=<mi\; mathvariant="normal">⌜</mi>M<mi\; mathvariant="normal">⌝</mi>$ and the current configuration code. After each return, it reads the decoded state component of that configuration code. If the state is accepting, $R$ accepts. If the state is rejecting, $R$ rejects. Otherwise it feeds the returned successor configuration back into the next interpreter call.

By [L3], each iteration in step 2.1 maintains exactly the current configuration of $M$ on $w$. Therefore $R$ accepts precisely when $M$ eventually reaches an accepting configuration on $w$, rejects when $M$ reaches a rejecting configuration, and diverges when $M$ diverges. By [L1] and [L5], this means that $R$ recognizes $A_{TM}$.

Construct a deterministic one-tape machine $D_H$ with input alphabet ${\mathrm{\Sigma }}_2$ as follows. On input a word $y\in {\mathrm{\Sigma }}_2^{\ast }$, first check whether every symbol is $1$ or $2$ and, if so, recover the unique binary word $x$ obtained by replacing $1$ by $0$ and $2$ by $1$. Use [L2] to decode $x$ as a candidate machine code. If $x$ is malformed or decodes to a machine whose input alphabet does not contain both symbols $1$ and $2$, reject. Otherwise form the coded pair $⟨x,\widehat{\bar{x}}⟩$ and run $H$ on that binary input. If $H$ accepts, then loop forever; if $H$ rejects, then accept. This machine is effective because the recoding $x\leftrightarrow \bar{x}$, the machine-code decoder, and the call to $H$ are all effective, and [L3] guarantees that the call to $H$ halts.

Let $M$ be any coded deterministic one-tape Turing machine whose input alphabet contains ${\mathrm{\Sigma }}_2$, and put $x=<mi\; mathvariant="normal">⌜</mi>M<mi\; mathvariant="normal">⌝</mi>$. On input $\bar{x}$, the preliminary checks in step 1.1 succeed, and the query sent to $H$ is exactly $⟨<mi\; mathvariant="normal">⌜</mi>M<mi\; mathvariant="normal">⌝</mi>,\widehat{\bar{x}}⟩=⟨<mi\; mathvariant="normal">⌜</mi>M<mi\; mathvariant="normal">⌝</mi>,\widehat{\overline{<mi\; mathvariant="normal">⌜</mi>M<mi\; mathvariant="normal">⌝</mi>}}⟩$. By [L1] and the correctness of the decider $H$ from [L3], $H$ accepts that query exactly when $M$ accepts $\bar{x}$. Because $D_H$ does the opposite of $H$'s answer, $D_H$ accepts $\bar{x}$ exactly when $M$ does not accept $\bar{x}$.

Step 2.1 is exactly the required diagonal property. Therefore the constructed machine $D_H$ exists.

Assume for contradiction that $A_{TM}$ is decidable. Then [L1] gives a deterministic decider $H$ for $A_{TM}$. Apply [L2] to that $H$ and obtain the corresponding machine $D_H$. Because $D_H$ itself has input alphabet ${\mathrm{\Sigma }}_2$, the diagonal equivalence from [L2] applies to $M=D_H$.

Let $d=<mi\; mathvariant="normal">⌜</mi>D_H<mi\; mathvariant="normal">⌝</mi>$, whose existence is guaranteed by [L3]. Substituting $M=D_H$ into [L2] yields $D_H\text{ accepts }\bar{d}⟺D_H\text{ does not accept }\bar{d}$. That is impossible.

The contradiction in step 2.1 discharges the assumption from step 1.1. Therefore $A_{TM}$ is undecidable.

Recognizability: build a deterministic one-tape machine $R$ that, on input $z$, first parses $z$ as a candidate pair $⟨x,y⟩$. If the pair parse fails, it rejects. It next runs the decider from [L4] on $x$; if $x$ is not a well-formed machine code, it rejects. If $x$ is valid, it uses [L2] to recover the coded machine $M=(m,s,n,\tau )$. It then parses $y$ as a candidate word code $c(\mathrm{bin}(\mathrm{\ell }))c(\mathrm{bin}(a_1))\cdots c(\mathrm{bin}(a_{\mathrm{\ell }}))$, rejects if that parse fails, and also rejects if some recovered symbol $a_i$ lies outside the input alphabet ${\mathrm{\Sigma }}_s=\{1,\dots ,s\}$. From the recovered word $w=a_1\cdots a_{\mathrm{\ell }}$, the machine writes the canonical initial configuration code of $M$ on input $w$.

Undecidability: if $HAL{T}_{TM}$ were decidable, then by [L5] there would be a deterministic decider $K$ for $HAL{T}_{TM}$. Given an input $⟨<mi\; mathvariant="normal">⌜</mi>M<mi\; mathvariant="normal">⌝</mi>,\widehat{w}⟩$ for $A_{TM}$, effectively build a machine $N_{M,w}$ that ignores its own input, simulates $M$ on $w$, halts and accepts if that simulation accepts, and otherwise loops forever. Then $⟨<mi\; mathvariant="normal">⌜</mi>M<mi\; mathvariant="normal">⌝</mi>,\widehat{w}⟩\in A_{TM}⟺⟨<mi\; mathvariant="normal">⌜</mi>N_{M,w}<mi\; mathvariant="normal">⌝</mi>,\widehat{\epsilon }⟩\in HAL{T}_{TM}$. Indeed, $N_{M,w}$ halts on the blank input exactly in the case that $M$ accepts $w$. So the assumed decider $K$ would decide $A_{TM}$, which [L7] forbids.

The machine $R$ now repeatedly invokes the one-step interpreter from [L3] on the pair consisting of the recovered code $x=<mi\; mathvariant="normal">⌜</mi>M<mi\; mathvariant="normal">⌝</mi>$ and the current configuration code. After each return, it reads the decoded state component of that configuration code. If the state is accepting or rejecting, $R$ accepts. Otherwise it feeds the returned successor configuration back into the next interpreter call.

By [L3], each iteration in step 2.1 maintains exactly the current configuration of $M$ on $w$. Therefore $R$ accepts precisely when $M$ eventually reaches an accepting or rejecting configuration on $w$, and diverges when $M$ diverges. By [L1], [L5], and [L6], this means that $R$ recognizes $HAL{T}_{TM}$.

Steps 3.1 and 1.2 prove recognizability and undecidability, respectively. Therefore $HAL{T}_{TM}$ is recognizable and undecidable.

Suppose for contradiction that the complement of $HAL{T}_{TM}$ were recognizable. Then both $HAL{T}_{TM}$ and its complement would be recognizable, by [L1].

Applying [L2] to step 1.1 would make $HAL{T}_{TM}$ decidable. That contradicts the undecidability clause of [L1].

Therefore the complement of $HAL{T}_{TM}$ is not recognizable.

By [L2], the complement of $HAL{T}_{TM}$ is itself a language.

By [L1], that language is not recognizable, and [L3] identifies this as exactly the existence claim wanted.

By [L1], choose a deterministic machine $F$ that, on input $\mathrm{bin}(n)$, halts with output $\mathrm{bin}(f(n))$. For each $n\in \mathbb{N}$, build a new machine $P_n$ that has the binary digits of $n$ hard-wired into a straight-line prefix of its finite control, using one additional state per written digit and then handing control to a fixed simulation of $F$. On blank input, $P_n$ writes the binary numeral for $n$ onto its tape, runs $F$ on that input until $F$ halts with output $\mathrm{bin}(f(n))$, and then runs a fixed binary-counter routine for $f(n)+1$ iterations before halting. Therefore $P_n$ halts on the blank input, and its total running time is strictly greater than $f(n)$.

Write $L_n:=\mathrm{\mid }\mathrm{bin}(n)\mathrm{\mid }$. The construction in step 1.1 uses at most $a+b{L}_n$ states and a fixed tape alphabet, for constants $a,b$ depending only on $F$ and the fixed routines. In the concrete code of [L3], this gives $O(L_n)$ transition triples, and every state numeral in those triples has length $O({\log }_2(L_n+2))$. The self-delimiting tuple encoding therefore gives constants $A,B\in \mathbb{N}$ such that $\mathrm{\mid }<mi\; mathvariant="normal">⌜</mi>P_n<mi\; mathvariant="normal">⌝</mi>\mathrm{\mid }\le A+B{L}_n{\log }_2(L_n+2)$. Since $L_n\le 1+{\log }_2(n+1)$, the right-hand side is $O(\log n\log \log (n+2))$, so there exists $N$ such that $\mathrm{\mid }<mi\; mathvariant="normal">⌜</mi>P_n<mi\; mathvariant="normal">⌝</mi>\mathrm{\mid }\le n$ whenever $n\ge N$. For those $n$, the machine $P_n$ is among the competitors counted by $BB(n)$.

If $n\ge N$, then step 2.1 puts $P_n$ inside the size budget for $BB(n)$, and step 1.1 gives a halting time larger than $f(n)$. By [L2], the maximum $BB(n)$ is therefore at least that halting time, so $BB(n)\ge f(n)$. Thus $BB$ eventually dominates $f$.

Suppose for contradiction that $BB$ were computable in the sense of [L2]. Then the function $g(n):=BB(n)+1$ would also be total computable.

Applying [L1] to the computable function $g$ yields an $N$ such that $BB(n)\ge g(n)=BB(n)+1$ for every $n\ge N$. That is impossible.

Therefore $BB$ is not computable.

First decide whether the input $z$ is a valid code $⟨<mi\; mathvariant="normal">⌜</mi>M<mi\; mathvariant="normal">⌝</mi>,\widehat{w}⟩$, including whether $w$ is over $M$'s input alphabet. This is effective by the chosen decoders. If it is malformed, map $z$ to the code of a fixed machine that halts on every input; such a $z$ is outside $HAL{T}_{TM}$. For a valid pair, effectively build a machine $T_{M,w}$ with input alphabet ${\mathrm{\Sigma }}_1=\{1\}$ as follows. On input $x$, the machine simulates $M$ on $w$ for exactly $\mathrm{\mid }x\mathrm{\mid }$ steps. If the simulation has not halted by then, $T_{M,w}$ halts and accepts. If the simulation has halted within those $\mathrm{\mid }x\mathrm{\mid }$ steps, then $T_{M,w}$ enters an infinite loop. This construction is effective by [L2].

For a valid pair, if $M$ never halts on $w$, then every finite step-bounded simulation in step 1.1 remains nonhalting, so $T_{M,w}$ halts on every input $x$. Conversely, if $M$ halts on $w$ after exactly $t$ steps, then for every input $x$ with $\mathrm{\mid }x\mathrm{\mid }\ge t$ the machine $T_{M,w}$ detects that halting event during its first $\mathrm{\mid }x\mathrm{\mid }$ simulated steps and therefore loops forever. Thus the reduction preserves membership in the complement of $HAL{T}_{TM}$ for valid pairs. The fixed total-machine output in the malformed case preserves membership there as well.

Suppose for contradiction that $TO{T}_{TM}$ were recognizable. On any input $z$, compute the corresponding total-machine or $T_{M,w}$ code from step 1.1 and run the assumed recognizer for $TO{T}_{TM}$ on that code. By step 2.1, this would recognize the full complement of $HAL{T}_{TM}$, including malformed codes, contradicting [L1]. Therefore $TO{T}_{TM}$ is not recognizable, by [L3].

Fix once and for all a coded deterministic machine $A$ that accepts every input. Given an instance $⟨<mi\; mathvariant="normal">⌜</mi>M<mi\; mathvariant="normal">⌝</mi>,\widehat{w}⟩$ of $HAL{T}_{TM}$, use [L2] to build a machine $E_{M,w}$ that ignores its own input, simulates $M$ on $w$, accepts every input if that simulation ever halts, and otherwise loops forever on every input.

If $M$ halts on $w$, then every input to $E_{M,w}$ eventually triggers acceptance, so [L1] gives $L(E_{M,w})={\mathrm{\Sigma }}^{\ast }$. If $M$ does not halt on $w$, then $E_{M,w}$ accepts no input at all, so $L(E_{M,w})=\mathrm{\varnothing }$. Therefore $⟨<mi\; mathvariant="normal">⌜</mi>M<mi\; mathvariant="normal">⌝</mi>,\widehat{w}⟩\in HAL{T}_{TM}⟺⟨<mi\; mathvariant="normal">⌜</mi>E_{M,w}<mi\; mathvariant="normal">⌝</mi>,<mi\; mathvariant="normal">⌜</mi>A<mi\; mathvariant="normal">⌝</mi>⟩\in E{Q}_{TM}$.

Suppose for contradiction that $E{Q}_{TM}$ were decidable. Then step 2.1 would let that decider decide $HAL{T}_{TM}$, contradicting [L3]. Hence $E{Q}_{TM}$ is undecidable, by [L4].

Let $M_{\mathrm{y}\mathrm{e}\mathrm{s}}$ be the machine that immediately enters its accepting state on every input. Then, by [L2], the specific coded pair $⟨<mi\; mathvariant="normal">⌜</mi>M_{\mathrm{y}\mathrm{e}\mathrm{s}}<mi\; mathvariant="normal">⌝</mi>,\widehat{1}⟩$ lies in $A_{TM}$, and this yes-answer is completely explicit.

Step 1.1 shows that at least one individual instance of $A_{TM}$ is easy to answer, while [L1] says the whole language is still undecidable. So undecidability cannot mean that every particular instance is beyond analysis; it means only that no single algorithm decides all instances.

By [L1] and [L3], the data needed for self-reference are only a finite description string and a fixed interpreter for that string. Nothing in those items mentions any physical source file, manuscript, or external text artifact.

The actual diagonal step in [L2] uses the coded pair $⟨<mi\; mathvariant="normal">⌜</mi>M<mi\; mathvariant="normal">⌝</mi>,\widehat{\overline{<mi\; mathvariant="normal">⌜</mi>M<mi\; mathvariant="normal">⌝</mi>}}⟩$, not a literal reading of source text. So the contradiction is carried entirely by effective encoding and simulation.