Saturday 10 April 2010

Self Rep

What is the output of this python program self_rep.py?


def self_rep(a): print a; print 'self_rep('+chr(34)+a+chr(34)+')'
self_rep("def self_rep(a): print a; print 'self_rep('+chr(34)+a+chr(34)+')'")


Try "cat self_rep.py", "cat self_rep.py | python", "cat self_rep.py | python | python", ...

This self repeating program is a nice idea I found in the book "Gödel, Escher, Bach" by D.R. Hofstadter. In general the book deals with how Gödel's incompleteness theorem Escher's drawings and Bach's music are related to the notion conciousness. By self-reference and self-repetition.

Gödel's string in plain language can be formulated as: "This sentence cannot be proven in number theory". It is apparently true (if it would be false it would be possible to prove it which means it would be true, which is a contradiction). Hence there is a true statement which cannot be proven. The other question is how this string can be a part of number theory - for that Gödel introduced his Gödel numbers. Finally, with a construction like the program above, he could have the string point at itself.

To finish this post, here is another program:


def self_inc(i,a): print a; print 'self_inc('+str(i+1)+','+chr(34)+a+chr(34)+')'
self_inc(1,"def self_inc(i,a): print a; print 'self_inc('+str(i+1)+','+chr(34)+a+chr(34)+')'")


Now you can try it again: "cat self_inc.py", "cat self_inc.py | python", "cat self_inc.py | python | python", ...

5 comments:

Noel O'Boyle said...

Cool, but the chr(34) business is confusing. You can just stick the " inside the '....' like print 'self_rep("' + a + '")' or even better, print 'self_rep("%s")' % a.

Felix said...

initially I tried something like your first suggestion. but i would need to put the extra " also into the argument of the function below. but i could not just put those because I already have " on the outside. and if I put \" it would not copy the \

the second one looks cool. i never quite understood this syntax though ... ;)

Noel O'Boyle said...

Then you should escape the escape the escape the escape....hmmm...maybe this is why we don't see many self referential programs these days. :-) BTW, you *need* to include this image in your post: http://depth-first.com/articles/2007/04/20/self-referential

Felix said...

maybe it would work if there was a shortcut for an infinite amount of escapes ...

that picture is pretty cool

Masters Thesis said...
This comment has been removed by a blog administrator.