Lagmental Vicfred

The Recursion Theorem Gives Programs Access to Their Own Description by Vicfred

Last updated: Mon 07 April 2025

tags: mathematics, computability, incompleteness, Turing machines

For every computable program transformer, some program has the same behavior as its transformed version. The example is deliberately concrete; it is a test of the statement, not a substitute for it.

Definitions first

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.

$$ f:\mathbf N\to\mathbf N\ \text{total computable} $$

The typography mirrors the proof: first declare \(\mathsf D\), then state \(\mathsf C\). The symbol \(\Longrightarrow\) below is a logical dependency, not extra mathematical structure.

$$ \exists e,\qquad\varphi_e=\varphi_{f(e)} $$

A small case in full

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

$$ \underbrace{e}_{\text{fixed program index}}\stackrel{f}{\longmapsto}\underbrace{f(e)}_{\text{transformed index}},\qquad\forall x\ \varphi_e(x)\simeq\varphi_{f(e)}(x) $$

The reusable statement

A good test for understanding is to change the presentation while keeping the invariant fixed. The aligned form makes that comparison unusually easy.

$$ \begin{aligned} \mathsf{D}\;&:\quad f:\mathbf N\to\mathbf N\ \text{total computable},\\[5pt] \mathsf{C}\;&:\quad \exists e,\qquad\varphi_e=\varphi_{f(e)}. \end{aligned} $$

A nearby false statement

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

$$ \boxed{\begin{gathered} \text{compact conclusion}\\[-2pt] \exists e,\qquad\varphi_e=\varphi_{f(e)} \end{gathered}} $$

I would use the boxed line as a reference later, while returning to the full display whenever a hypothesis becomes uncertain. That division keeps compression from becoming ambiguity.

This article was posted on Thu 12 December 2024. Facts and circumstances may have changed since publication.
Please contact me before jumping to conclusions if something seems wrong or unclear.