Random Self-modifiable Computation

A new computational model, called the ex-machine, executes standard instructions, meta instructions, and random instructions. Standard instructions behave similarly to machine instructions in a digital computer. Meta instructions self-modify the ex-machine’s program during its execution. We construct a countable set of ex-machines; each can compute a Turing incomputable language, whenever the quantum random measurements in the random instructions behave like unbiased Bernoulli trials. In 1936, Turing posed the halting problem and proved that this problem is unsolvable for Turing machines. Let \(\{({M}_i, T_i): i \in \mathbb {N} \}\) be a Turing computable enumeration of all Turing machines M _i and finite tapes T _i. Does there exist an ex-machine \(\mathcal {X}\) that has at least one evolutionary path \(\mathcal {X} \rightarrow \mathcal {X}_1 \rightarrow \mathcal {X}_2 \rightarrow \dots \rightarrow \mathcal {X}_m\), so at the mth stage, the ex-machine \(\mathcal {X}_m\) can correctly determine for 0 ≤ i ≤ m whether M _i’s execution on tape T _i eventually halts? We construct an ex-machine Z(x) that has one such evolutionary path; at stage m, Z(x) has used a finite amount of computational resources. The existence of this path suggests that David Hilbert (Nachrichten von der Gesellschaft der Wissenschaften zu Göttingen, Mathematische-Physikalische Klasse. 3:253–297, 1900) may not have been misguided to propose that mathematicians search for finite methods to help construct proofs. Our refinement is to not use a program that behaves according to a fixed set of mechanical rules. We must pursue computation that exploits randomness and self-modification so that the complexity of the program can increase during computation.