Friday, June 15, 2007

A program that prints itself

Update 17th July 2007: Rummaging through my notes I found this - This is a corollary of the Recursion Theorem. This is the way a virus can get a description of itself and print it to a file and do other "wonderfull" stuff to itself like - mutate. Check out this interesting article that talks in detail about the Recursion Theorem - Link

I had been told that any Turing Machine can be made to print itself. Programs are Turing Machines, so they should be able to print themselves. I never actually tried to write such a program myself.

Getting into an argument with some colleagues, I got cornered into defending my statement with a (at the moment) running program or retract my statement. So, with trembling hands, a vague memory of description of such a machine during one of the lectures I attended once and copious amounts of faith in the professor, I gave it a shot. And by golly I got it right ...

Let me lay the ground first.

The program
#include<stdio.h>
main() { printf("Hello, world");}

Prints:
Hello, world
Should print:
#include<stdio.h>
main() { printf("Hello, world");}

To make a program print itself one can attempt:

The program
#include<stdio.h>
main() { printf("#include<stdio.h>\nmain() { printf(\"#include<stdio.h>\n main() { ...\") } ");}

Prints:
#include<stdio.h>
main() { printf("#include<stdio.h>
main() { ...") }

Should Print:
#include<stdio.h>
main() { printf("#include<stdio.h>\nmain() { printf(\"#include<stdio.h>\n main() { ...\") } ");}

So, one gets into a mirror reflecting a mirror kind of a situation.

A program to print its own description:
#include<stdio.h>
main(){ char *str="printf(\"#include<stdio.h>%cmain\(){char *str=%c%str%c; \",10,str,34,34); printf(\"%s\",str); printf(\"}\");"; printf("#include<stdio.h>%cmain\(){char *str=%c%str%c; ",10,34,str,34); printf("%s",str); printf("}"); }

Prints:
#include<stdio.h>
main(){char *str="printf("#include<stdio.h>%cmain(){char *str=%c%str%c; ",10,str,34,34); printf("%s",str); printf("}");tr"; printf("#include<stdio.h>%cmain(){char *str=%c%str%c; ",10,str,34,34); printf("%s",str); printf("}");}

The general idea is like this:

[PartXBegin] = main() { char *str=[PartY];
[PartY] = <Print [PartXBegin]> <Print str> <Print [PartXEnd]>
[PartXEnd] = }

Any program can print a description of itself (obviously,only if it can at least perform the basic turing operations).

7 comments:

Anonymous said...

This is great info to know.

Anonymous said...

this is stolen stuff!
some famous person wrote this code...
its called 'quine'...

Dev's Lab said...

Well, I never said I discovered or invented this. I merely recollected what I had seen or heard in college a long time back (read the post).

The C code here was impromptu. I don't think I had seen that before.

Thanks for sharing information about Quine. Interesting
http://en.wikipedia.org/wiki/Willard_Van_Orman_Quine

Dev

Anonymous said...

There are a couple of interesting points over time in this article but I do not determine if these people center to heart. There exists some validity but I’m going to take hold opinion until I investigate it further. Very good post , thanks and that we want more! Added to FeedBurner likewise

Anonymous said...

It’s really a cool and useful piece of info. I’m glad that you shared this useful info with us. Please keep us informed like this. Thanks for sharing.

Anonymous said...

Gօod site уou have goot here.. It's difficult tο find Һigh-quality writing lіke yourѕ tbese
days. І really apрreciate individuals like yоu!
Taқе care!!

my web-site: easy

Anonymous said...

If yyou wish for to grow your familiarity simply keep visiting this web pzge and bee updated wih the newest
information posteed here.