Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!usc!apple!netcomsv!doug
From: doug@netcom.COM (Doug Merritt)
Newsgroups: comp.lang.misc
Subject: Re: Halting Problem Solved! Film at 11! (Was Re: definitions)
Summary: "Finite programs haltable?" is solvable
Message-ID: <1991May22.174414.7146@netcom.COM>
Date: 22 May 91 17:44:14 GMT
References: <1991May5.135342.13792@daffy.cs.wisc.edu> <30164@dime.cs.umass.edu> <1991May18.225337.24416@sbcs.sunysb.edu>
Organization: Netcom - Online Communication Services  UNIX System {408 241-9760 guest}
Lines: 27

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