Lagmental Vicfred

The Halting Problem Defeats a Diagonal Decider by Vicfred

Assuming a total halting decider lets a program reverse the predicted behavior on its own code. I want the notation, the mechanism, and the failure mode visible at the same time.

Start locally

A decision problem is computable when a Turing machine \(M_e(x)\) halts on every input with the correct answer. A set \(A\subseteq\mathbf N\) is computably enumerable when a machine can list its members.

$$ H(e,x)=\begin{cases}1,&M_e(x)\text{ halts},\\0,&M_e(x)\text{ does not halt},\end{cases} $$

I keep the defining relation \(\mathsf D\) above the derived relation \(\mathsf C\). This exposes whether cancellation used \(x\ne0\) and whether the conclusion is canonical.

$$ H\ \text{is not computable} $$

Compute before generalising

The following line is the smallest calculation that still exercises the mechanism. It keeps nested delimiters and the order of operations explicit.

$$ D(e)=\begin{cases}\text{loop forever},&H(e,e)=1,\\\text{halt},&H(e,e)=0,\end{cases}\qquad D(\langle D\rangle)\ \text{contradicts either answer} $$

The global view

What survives the example is not its particular numbers but the relation encoded by the two rows below. That relation is the part worth transporting to a new setting.

$$ \begin{aligned} \mathsf{D}\;&:\quad H(e,x)=\begin{cases}1,&M_e(x)\text{ halts},\\0,&M_e(x)\text{ does not halt},\end{cases},\\[5pt] \mathsf{C}\;&:\quad H\ \text{is not computable}. \end{aligned} $$

Edge conditions

Enumerability is weaker than decidability. A search may confirm membership eventually without ever certifying nonmembership.

$$ \boxed{\begin{gathered} \text{compact conclusion}\\[-2pt] H\ \text{is not computable} \end{gathered}} $$

The final box is a summary, not a new assumption; the proof still lives in the definitions and the intervening calculation. The source keeps each scope delimiter visible for later inspection.

This article was posted on Fri 21 August 2015. Facts and circumstances may have changed since publication.
Please contact me before jumping to conclusions if something seems wrong or unclear.