Path: utzoo!news-server.csri.toronto.edu!cs.utexas.edu!usc!rpi!sarah!bingnews!kym
From: kym@bingvaxu.cc.binghamton.edu (R. Kym Horsell)
Newsgroups: comp.lang.c
Subject: Re: Small introspective program
Message-ID: <1991Mar16.163213.9794@bingvaxu.cc.binghamton.edu>
Date: 16 Mar 91 16:32:13 GMT
References: <1991Mar13.001423.5194@Think.COM> <4963@goanna.cs.rmit.oz.au> <217@hermix.UUCP>
Organization: State University of New York at Binghamton
Lines: 57

In article <217@hermix.UUCP> jay@hermix.UUCP (Jay Skeer) writes:
[about a program that recognises itself]


Ok, that's nice. Why not progress to the stage of writing programs
that write self-recognising programs?

The following is a (probabalistic) example. It relies on fixpoint
theory to guarantee finding the appropriate parameters (in fact the
search for any self-replicating automaton can use this theory) and 
terminates in several iterations.

Of course the output program is not guaranteed to recognise only
itself -- it also can be fooled by `family members'.

Question -- what is another legal C program that the `recogniser'
thinks is similar to itself?

Have fun y'all.

-kym
--- Program to find self-recognising program ---
#include <stdio.h>

char buf[1000];
char *prog=
"main(){int MAGIC=0x%x,c,i=0,s=0;while((c=getchar())>=0)s+=s^(c<<(i++&15));puts(s==MAGIC?\"maybe\":\"no\");}\n";

int sum(MAGIC) {
	int c,i=0,sum=0;
	char *cp=buf;
	sprintf(buf,prog,MAGIC);
	while(c= *cp++) sum+=sum^(c<<(i++&15));
	return sum;
	}

main(){
	int MAGIC=0,NEWMAGIC;

	for(;;) {	
		NEWMAGIC=sum(MAGIC);
		printf("NEWMAGIC=0x%x\n",NEWMAGIC);
		if(NEWMAGIC==MAGIC) break;
		MAGIC=NEWMAGIC;
		}
	fputs(buf,stdout);
	exit(0);
	}
--- self-recognising program found by above ---
main(){int MAGIC=0x40116000,c,i=0,s=0;while((c=getchar())>=0)s+=s^(c<<(i++&15));puts(s==MAGIC?"maybe":"no");}
--- sample run ---
cc t.c
a.out < t.c
maybe
a.out < a.out
no
--- end ---