4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ I think it should be something using Kleene fixed point theorem $\endgroup$ – KirillSk Dec 1 '14 at 12:40
2
$\begingroup$

You maybe know the recursion theorem. It implies, that you can assume that you have a procedure called get_your_own_codeif your programming language is at least as powerful as a Turing machine.

Now do the following

Progr. A
w=get_your_own_code
print "print "+w

Note that some code is hidden in the subroutine of get_you_own_code. So we assume the complete source code is a string called source_code_of_A.

Progr. B
print source_code_of_A

Program A prints:

  print source_code_of_A

Program B prints

  source_code_of_A
| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I did not get it. Could you explain it more? In particular, why does program $A$ produce that output? $\endgroup$ – hengxin Dec 1 '14 at 13:03
  • $\begingroup$ That's what I was looking for! $\endgroup$ – KirillSk Dec 1 '14 at 13:07
  • $\begingroup$ Your remark about the recursion theorem is not accurate. The recursion theorem allows you to get your own code, but at the cost of moving to a different program, a syntactically different program, but one that is equivalent to the given program in that it computes the same function. This difference seems to break this solution, since you are really only producing programs A and B, such that A writes a program that is equivalent to (rather than identical to) B and vice versa. But in a system with a genuine get_your_own_code, then this solution is fine. See mathoverflow.net/a/188527/1946. $\endgroup$ – JDH Dec 1 '14 at 21:40
  • $\begingroup$ @JDH Thanks for the pointer. I agree this was a bit sloppy. I fixed the answer. $\endgroup$ – A.Schulz Dec 2 '14 at 7:32
2
$\begingroup$

We will show that any Turing-complete "programming language" has such a pair of programs by using classic recursion theory, that is the notions of Gödel numberings with s-m-n property/theorem (smn) and Kleene's fixed-point/recursion theorem (FPT).
Denote with $\mathcal{P}$ the set of all (partially) recursive functions and with $\mathcal{R}$ the set of all total recursive functions.

We interpret "program $A$ outputs the code of program $B$" to mean

$\qquad\displaystyle \forall x.\ \varphi_A(x) = B$, i.e. $\varphi_A = \bigl[x \mapsto B\bigr]$;

in our setting $A, B \in \mathbb{N}$.

So let $\varphi$ an arbitrary Gödel numbering (with smn) of $\mathcal{P}$. From

$\qquad\displaystyle f = \bigl[(i,x) \mapsto i\bigr] \in \mathcal{P} $

we get with the s-m-n theorem that there is $g \in \mathcal{R}$ so that

$\qquad\displaystyle \varphi_{g(i)} = \bigl[x \mapsto i\bigr] \;. $

Now we are essentially looking for a fixed point of $g \circ g$, i.e. $a$ so that $\varphi_{g(g(a))} = \varphi_{a} = \bigl[x \mapsto g(a)\bigr]$; recall that $\varphi_{g(a)} = \bigl[x \mapsto a\bigr]$.
This is easy to obtain by FPT, but we also need that $g(a) \neq a$ -- otherwise we just have a regular quine, not a pair of programs as required.

Therefore, we define¹ a "modified $g \circ g$" by

$\qquad\displaystyle h(j) = \begin{cases} g(g(j)) &, g(j) \neq j \\ g(j+1) &, g(j) = j \end{cases} \;,$

and $h \in \mathcal{R}$ since $g \in \mathcal{R}$. Now FPT yields

$\qquad\displaystyle \exists\, a.\ \varphi_{h(a)} = \varphi_a \;.$

Now we know by construction of $h$ that $g(a) \neq a$. For a proof, note that assuming $g(a) = a$ leads immediately to

$\qquad\displaystyle \bigl[x \mapsto a\bigr] = \varphi_{g(a)} = \varphi_a = \varphi_{h(a)} = \varphi_{g(a+1)} = \bigl[x \mapsto a+1\bigr] \;, $

a contradiction. So we can now let $b = g(a) \neq a$ and obtain as final result

\begin{align*} \varphi_b &= \varphi_{g(a)} = \bigl[x \mapsto a\bigr] \quad\text{and} \\ \varphi_a &= \varphi_{h(a)} = \varphi_{g(g(a))} = \bigl[x \mapsto g(a) = b\bigr] \;. \end{align*}

Credits go to a friend of mine who, after some fruitless tinkering on both of our parts, came up with the final idea.


  1. Note that the second case is not unique; all we need is an index other than $j$. Using $g$ is convenient since we know what it does on every parameter.
| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.