Return Styles: Pseud0ch, Terminal, Valhalla, NES, Geocities, Blue Moon. Entire thread

Anal Turing was wrong

Name: Anonymous 2011-02-04 8:45

There are at most 2^n different programs of length n (in binary).

Those that terminate go on forever, those that don't terminate stop after x steps.

let f(n) = the largest x.

Now write the program:

halts?(program) {
 int maxsteps = f(length(program));
 for(int i = 0; i < maxsteps; i++) { step(program); }
 if(halted?(program)) return HALTS;
 else return LOOPS;
}


any questions Turing?

Name: Anonymous 2011-02-06 21:38

Why don't we just leave programs that never stop running until they do? just clear out the cache and free up RAM from time to time.

Newer Posts
Don't change these.
Name: Email:
Entire Thread Thread List