patternMinor
Prove existence of different programs printing each other code
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
Now do the following
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
Program A prints:
Program B prints
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 "+wNote 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_AProgram A prints:
print source_code_of_AProgram B prints
source_code_of_ACode Snippets
Progr. A
w=get_your_own_code
print "print "+wProgr. B
print source_code_of_Aprint source_code_of_Asource_code_of_AContext
StackExchange Computer Science Q#33685, answer score: 2
Revisions (0)
No revisions yet.