HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Prove existence of different programs printing each other code

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
eachexistencedifferentproveprintingprogramscodeother

Problem

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?

Solution

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

Code Snippets

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

Context

StackExchange Computer Science Q#33685, answer score: 2

Revisions (0)

No revisions yet.