🚀 go-pugleaf

In article <1991May18.225337.24416@sbcs.sunysb.edu> jallen@eeserv1.ic.sunysb.edu (Joseph Allen) writes:
>
>But this is getting a little silly.  Whether finite programs are haltable is
>also unprovable (right? CS people?).

Untrue. For any finite program A of size N bits (with number of states = 2^N),
there exists (in a mathematical sense) another finite program B with a
lookup table of size 2^N (each entry corresponds to a state) which says
whether A will halt when in some particular state.

Similarly, for *all* finite programs A* with size < N bits (that as usual
start in a particular known state), there exists a finite program C with a
looktable of size 2^N (each entry corresponds to a program) that says whether
each program in A* must eventually halt.

This reasoning does not work on all programs, because that is an infinite
set including unboundedly large programs and therefore a lookup table
would have to be aleph-1 in size.

For a program with 4 Megabytes (2^25 bits) of memory, one would need a
lookup table of size 2^(2^25) bits, making this a bit unrealistic in
practice.

Generating the lookup tables is left as an exercise for the reader. :-)
	Doug
-- 
Doug Merritt	doug@netcom.com		apple!netcom!doug