Suggest edit — Self-Reference

Title

Name

Note

---
title: "Self-Reference"
type: concept
related: [Turing Machinea]
source: https://www.jemoka.com/posts/kbhself_reference/
confidence: high
status: active
---

There is a Self-Printing Turing Machine Q There&rsquo;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 &ldquo;get your own code&rdquo;.
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.
&ldquo;i.e. there is free will&rdquo; (jk)&mdash;no machine can predict the output of all others.