User:IssaRice/Computability and logic/Rogers fixed point theorem using Sipser's notation

Sipser's textbook presents the recursion theorem, but not the fixed point theorem. Here is one way to state the fixed point theorem using Sipser's notation.

Theorem (Fixed point theorem). Let $F$ be a Turing machine which computes a function $f:\Sigma ^{*}\to \Sigma ^{*}$ . Then there exists a Turing machine $R$ which computes a function $r:\Sigma ^{*}\to \Sigma ^{*}$ , and a Turing machine $T$ which computes a function $t:\Sigma ^{*}\to \Sigma ^{*}$ , such that $f(\langle R\rangle )=\langle T\rangle$ and $r(w)=t(w)$ for all $w\in \Sigma ^{*}$ .

Remark. This is basically a "curried" version of the recursion theorem. Instead of $r(w)=f(\langle R\rangle ,w)$ , we have (with abuse of notation) $r(w)=f(\langle R\rangle )(w)$ .

The proof is pretty similar to the one in Sipser's book. We build $R$ in four parts, $A,B,F,E$ , where:

$A$ is $P_{\langle BE\rangle }$
$B$ $B$ is the Turing machine that, on input $w,\langle M\rangle$ $w,\langle M\rangle$ :
- computes $q(\langle M\rangle )$
- combines the result with $\langle M\rangle$ to make a complete Turing machine
- prints $w$ along with the description of this Turing machine and halts, i.e. outputs $w,q(\langle M\rangle )\langle M\rangle$
$E$ $E$ is an "eval" Turing machine that, on input $w,\langle M\rangle$ $w,\langle M\rangle$ :
- changes the tape contents to $\langle M\rangle$
- runs $F$ , and stores the result as $\langle T\rangle$
- changes the tape contents to $w$
- runs $T$

Given input $w$ , what does $R$ do? First $A$ runs, and prints $\langle BE\rangle$ after the input. After $A$ runs, the tape contains $w,\langle BE\rangle$ . Next, $B$ runs. $B$ computes $q(\langle BE\rangle )=\langle A\rangle$ and combines this with $\langle BE\rangle$ . Thus, after $B$ finishes, the tape contains $w,\langle ABE\rangle =w,\langle R\rangle$ . Finally $E$ runs. It first runs $F$ with input $\langle ABE\rangle =\langle R\rangle$ , and stores $\langle T\rangle =f(\langle R\rangle )$ . Then it runs $T$ on $w$ , which results in $t(w)$ being left on the tape at the end. Since this is the final output of $R$ given the input $w$ , we have $r(w)=t(w)$ .

See also