Prove existence of different programs printing each other code 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.
 A: You are looking for quines.
It's so boring to use the recursion theorem when one can just enjoy Dan Piponi's Haskell program that prints out a Perl program that prints out a Python program that prints out a Ruby program that prints out a C program that prints out a Java program that prints out the original program. And it's just 200 lines of Haskell code, see this paste.
A: 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
A: You can obtain this directly from the recursion theorem as follows: Consider $f(x,y)=x$. By s-m-n, this equals $\varphi_{s(x)}(y)$. We can also demand (by padding) that $s(x)>x$. By the recursion theorem, applied to $g(x,y)=s(x)$, there is an $e$ such that $\varphi_e(y)=s(e)$. The programs $e, s(e)$ print each other.
