Codes

[A23]

Hi,

what would happen if i let run a program that writes and run all possible program in the order ?

[CraigD]

what would happen if i let run a program that writes and run all possible program in the order ?

You’d find something similar, I’m pretty confident, to what Roger Penrose reported in his 1989 book The Emperor’s New Mind. I wrote a little bit about this in Resolving ambiguous meaning of “algorithm” & Penrose’s Turing machine treatment.

 

In short, what Penrose did was write a Universal Turing Machine – not too unusual, in the 1980s or now, though challenging – with a binary (0s and 1s) alphabet – not usual, but not too unusual, either – then see what it did when given an initial tape (for a UTM, this consists of both the program to run, and its initial data) of every integer starting with 1. Most of them, as you might expect, don’t do anything useful, but some do.

 

The approach of systematically trying every possible program to find one that does a specific thing – or simply anything interesting – is an enticing one – give enough time, it must write every possible program – but suffers from the basic problem that even on very fast and massively parallel computers, it takes an impractically long time. For instance, assume that the shortest version of program you want is a modest 8196 bits long, and you have 1 trillion ([imath]10^{12}[/imath]) computers each capable of running and checking to see if it’s interesting 1 program in [imath]10^{16}[/imath] seconds (corresponding to something like 10 petaflops, the fastest yet built), this approach would take [imath]2^{8196} / 10^{28} \dot= 10^{280}[/imath] s to find . As the universe is less than about 13 billion years (on the order of [imath]10^{17}[/imath] s) old, this is a mind-bogglingly long time.

 

So, in short, if you let a program that writes and runs all possible programs in sequential order, it would likely not write a very interesting program your lifetime. If you let it generate large programs randomly, it might, but would be very unlikely, to.

[A23]

Most of the time it will probably generate error and may crash the computer ? This one did this.

[Theory5]

Uhh there seems to be an error in communication here (at least to me). A23, so you wrote a program to generate and run all possible programs but it crashes? What language did you use and can you show us the code?

[A23]

It's a technical curiosity but it seems has no practical use. It's C :

#include<stdio.h>

#include<stdlib.h>

#include<strings.h>

#include<string.h>

#include<sys/wait.h>

 

int main(int, char**);

 

// Generate all possible programs : open file, char addition +1, close, try to run

 

int main(int argc, char **argv)

{

FILE *prog;

bool finish=false;

unsigned char c[20];

 

if(argc==1)

{

printf("Generate all possible programsn Usage : %s filenamen",argv[0]);

printf("Write programs in 'filename'n");

}

else if(argc==2)

{

//test if file argv[1]

prog=fopen(argv[1],"rb");

if(!prog)

{

printf("File %s does not exist.nCreate it empty (y/n) ? ",argv[1]);

scanf("%2s",&c);

if(c[0]=='y')

{

prog=fopen(argv[1],"wb");

char start=0;

fwrite((char *)&start,sizeof(char),1,prog);

char cmd[256]="chmod u+x ";

strcat(cmd,argv[1]);

strcat(cmd,"n");

system(cmd);

fclose(prog);

 

printf("File %s was created.n Re-run %s %s to begin.n",argv[1],argv[0],argv[1]);

exit(0);

}

}

else

{

fclose(prog);

while(!finish)

{

 

//execute file

 

printf("Execute %s.n",argv[1]);

char cmd[256]="./";

strcat(cmd,argv[1]);

strcat(cmd,"n");

wait((void *)system(cmd));

//open file, add +1

 

char rest=(char)1;

prog=fopen(argv[1],"r+b");

while(!feof(prog))

{

fread(&c[0],1,sizeof(c[0]),prog);

printf("%1d->",(int)c[0]);

if((int)rest==1&&(int)c[0]<=254)

{

c[0]=(char)((int)c[0]+1);

rest=0;

}

if((int)rest==1&&(int)c[0]>254)

{

c[0]=0;

rest=1;

}

 

printf("%1d ",(int)c[0]);

fseek(prog,-sizeof(char),SEEK_CUR);

fwrite((char *)&c[0],1,sizeof(c[0]),prog);

fread(&c[0],1,sizeof(c[0]),prog);

}

if(rest==1)

fwrite((char *)&rest,1,sizeof(rest),prog);

fclose(prog);

//finish=true;

}

}

}

}

[Theory5]

I dont know much about C, very little in fact, but there are other members who excel at this stuff. I was attempting to run your code in Visual studio 2008 because I am curious and a bunch of stuff doesnt work. What are the files you are trying to include at the top? strcat and wait don't seem to be valid commands. Are you using a certain c language like C#?

[A23]

I used Linux c, maybe some libraries included differ.

[alexander]

not at all, visual studio is not quite iso compliant, and nor really is your code, but that aside, i don't see how that will generate "all the possible programs", you could make that a lot more efficient, because C code wording standard is defined fairly well... At this same rate you can write a function that will generate all the possible binaries, but it won't make it practical, nor will you, within your lifetime, find generate nearly enough programs, or be able to identify them to be able to say that you generated a useful program, a program that does something... that said, genetic algorithms and AI code is much, much more interesting and likely to generate useable programs for you, 1000 generations of self-evolving programs will take a few hours or maybe days to run, and a few months to go through, but you are many times more likely to find programs that actually do stuff, then what you propose above....

 

so let's not ponder this too much, and just write pretty code...