[Solved]: Prove existence of different programs printing each other code

Problem Detail: 

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?

Asked By : KirillSk

Answered By : A.Schulz

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 

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/33685

3.2K people like this

 Download Related Notes/Documents