There is a Self-Printing Turing Machine
Q
There’s a computable function \(q: \Sigma^{*} \to \Sigma ^{*}\) such that for every string \(w\), the computation \(q(w)\) produces the description of a Turing machine \(P_{w}\) such that on every input, it spits out \(w\) and then accepts.
B
For some turing machine code \(m\) making TM \(M\), the computable function \(B\) composes \(P_{m}\) from above and \(M\) (that is, the composition of \(P_{m}\) and \(M\) first disregards it input, prints \(m\), and give it to \(M\)).
Self-printing Turing machine
Consider now putting \(B\) through \(B\); we will then create a chain \(P_{B}\) and then \(B\); \(P_{B}\) on input will create the code for \(B\), and put it through \(B\), which will then make \(P_{B}\) and \(B\) again, and so on.
Recursion Theorem
For every Turing Machine, we can assume that it has access to some operation called “get your own code”.
For every Turing Machine \(T\) computing a function \(t: \Sigma^{*} \times \Sigma^{*} \to \Sigma^{* }\), there is a Turing machine \(R\) computing a function \(r: \Sigma^{ *} \to \Sigma^{*}\) such that for every string \(w\), we have \(r(w) = t(R,w)\).
That is, for every truing machine \(T\), there is another Turing Machine which can compute \(T\) where one of its slots is the source code for the \(T\) computation (i.e. \(R\)).
ATM is undecidable
Yet another proof. Woah. Smh.
Assume \(H\) decides \(A_{TM}\); Construct a machine \(B\) such that on input \(w\), we:
- obtain its own description \(B\) as in Recursion Theorem
- runs \(H(B,w)\) and flips the output
i.e. running \(B\) on \(w\) will return the opposite of \(B\) according to ATM.
“i.e. there is free will” (jk)—no machine can predict the output of all others.