2
$\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?

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.

$\endgroup$
17
  • 2
    $\begingroup$ Welcome to the site. This question does not appear to be a question directly related to mathemtical research (otherwise please provide that link via an edit). You might ask such a question on Computer Science or Mathematics But please check their respecitive FAQs and possibly add some more details to your question. $\endgroup$
    – user9072
    Dec 1, 2014 at 11:55
  • 2
    $\begingroup$ Interesting question! I think it is fine for MO. The answer is likely a species of the Kleene recursion theorem... $\endgroup$ Dec 1, 2014 at 12:24
  • 2
    $\begingroup$ I agree with JDH that this is not off-topic, but I think the question should be made more precise. Are we talking about a specific programming language? A class of programming languages? Why the prohibition on exhibiting examples? $\endgroup$ Dec 1, 2014 at 12:50
  • 7
    $\begingroup$ This is a neat problem, but I've seen this as a homework assignment in introductory computability theory courses, so I'm not sure this is appropriate for MO. (Still, I haven't voted to close.) $\endgroup$ Dec 1, 2014 at 13:06
  • 3
    $\begingroup$ Answered on CS cs.stackexchange.com/questions/33685/… $\endgroup$
    – user9072
    Dec 1, 2014 at 13:16

3 Answers 3

4
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ I believe that Raymond Smullyan has various instances of a doubled analogue of the recursion theorem (and tripled, etc.), which is what this argument amounts to. I think Smullyan has a whole book full of these, perhaps someone who knows can post the title. $\endgroup$ Dec 1, 2014 at 14:03
7
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ FWIW My starting point for that was to write a "formal" version of the code based on the description of the Recursion Theorem starting at p.42 of Vicious Circles by Barwise and Moss. Part of the reasoning is here: blog.sigfpe.com/2008/02/… $\endgroup$
    – Dan Piponi
    Dec 1, 2014 at 18:08
  • $\begingroup$ Yes, that is a nice example! The general method allows one systematically to produce such instances for any programming language at all, simply by picking appropriate functions $h_1$, $h_2$, $h_3$ and so on as in my answer. (Andrej, my solution didn't use the recursion theorem, but rather essentially re-proved this doubled version of it from scratch.) $\endgroup$ Dec 1, 2014 at 20:34
4
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Great! This is very nice. $\endgroup$ Dec 2, 2014 at 1:45
  • $\begingroup$ @JoelDavidHamkins: Thanks! I just noticed I didn't make sure in the first version that the two programs are distinct, but I've fixed this now. $\endgroup$ Dec 2, 2014 at 1:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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