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:{\mathrm{\Sigma }}^{*}\to {\mathrm{\Sigma }}^{*}$. Then there exists a Turing machine $R$ which computes a function $r:{\mathrm{\Sigma }}^{*}\to {\mathrm{\Sigma }}^{*}$, and a Turing machine $T$ which computes a function $t:{\mathrm{\Sigma }}^{*}\to {\mathrm{\Sigma }}^{*}$, such that $f(⟨R⟩)=⟨T⟩$ and $r(w)=t(w)$ for all $w\in {\mathrm{\Sigma }}^{*}$.

Remark. This is basically a "curried" version of the recursion theorem. Instead of $r(w)=f(⟨R⟩,w)$, we have (with abuse of notation) $r(w)=f(⟨R⟩)(w)$. This is the difference between $X\times Y\to Z$ and $X\to Z^Y$.

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

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

While $A$ depends on a description of $B$ and $E$, note that neither $B$ nor $E$ requires a description of $A$ (or of each other), so there is no circularity.

Given input $w$, what does $R$ do? First $A$ runs, and prints $⟨BE⟩$ after the input. After $A$ runs, the tape contains $w,⟨BE⟩$. Next, $B$ runs. $B$ computes $q(⟨BE⟩)=⟨A⟩$ and combines this with $⟨BE⟩$. Thus, after $B$ finishes, the tape contains $w,⟨ABE⟩=w,⟨R⟩$. Finally $E$ runs. It first runs $F$ with input $⟨ABE⟩=⟨R⟩$, and stores $⟨T⟩=f(⟨R⟩)$. 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)$.

Even though the statement of the proof makes it seem like we have to find R and T separately, this is actually not the case. Once we specify R, the description of T is given by $f(⟨R⟩)$.

Questions

• How does the proof here relate to the usual "abstract" proof of the Rogers fixed point theorem? e.g. the proof here does not make use of the diagonal function $d(x)={\phi }_x(x)$; is it somehow implicit in the proof? Conversely, the standard proof does not make use of an "eval" machine or Turing machines that print descriptions of other Turing machines. in particular, the specification of A and B has the kind of self-reference characteristic of quines. Where does this happen in the standard proof? Or are these proofs "essentially different" somehow?
• What happens if f ignores its input and goes into an infinite loop? What if f adds the line "print 'hello'" or adds 1 to whatever R computes?

See also

• https://machinelearning.subwiki.org/wiki/User:IssaRice/Computability_and_logic/Diagonalization_lemma#Rogers.27s_fixed_point_theorem