How to prove that there exist two different programs A and B such that A printing code of B and B printing code of A without giving actual examples of such programs?


Update: We could prove via Kleene's recursion theorem that there is program printing it's own code. I tried to apply similar technics but didn't succeed.



Prove existence of different programs printing each other code
Any Turing-complete model of computation will have programs with this property. Specifically, let $\varphi\_e$ denote the function computed by program $e$, in whatever such system you favor. Define two computable functions $h\_1$ and $h\_2$ so that


$$\varphi\_{h\_1(x,y)}(z)=\varphi\_x(x,y)\qquad\text{ and }\qquad\varphi\_{h\_2(x,y)}(z)=\varphi\_y(x,y).$$


That is, $h\_1(x,y)$ is a program that on input $z$ gives the value $\varphi\_x(x,y)$ and similarly for $h\_2$. We may easily arrange that $h\_1(x,y)\neq h\_2(x,y)$ for every $x,y$, that is, these programs are different (even if they might sometimes happen to compute the same function), simply by making irrelevant syntactic differences in $h\_1(x,y)$ versus $h\_2(x,y)$. 


Let $d\_1$ and $d\_2$ be the programs for these functions, so that
$\varphi\_{d\_1}=h\_1$ and $\varphi\_{d\_2}=h\_2$. Let
$$A=h\_1(d\_2,d\_1)\qquad\text{ and }\qquad B=h\_2(d\_2,d\_1).$$ These are different because we ensured that $h\_1$ and $h\_2$ always have different values. Now simply compute
$$\varphi\_A(z)=\varphi\_{h\_1(d\_2,d\_1)}(z)=\varphi\_{d\_2}(d\_2,d\_1)=h\_2(d\_2,d\_1)=B$$
and
$$\varphi\_B(z)=\varphi\_{h\_2(d\_2,d\_1)}(z)=\varphi\_{d\_1}(d\_2,d\_1)=h\_1(d\_2,d\_1)=A.$$


Thus, regardless of the input, program $A$ will output $B$, and program $B$ will output $A$, as desired.
as desired


