Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!usc!chaph.usc.edu!alcor.usc.edu!jeenglis
From: jeenglis@alcor.usc.edu (Joe English)
Newsgroups: comp.lang.misc
Subject: Re: Halting Problem Solved! Film at 11! (Was Re: definitions)
Message-ID: <17088@chaph.usc.edu>
Date: 4 May 91 20:56:48 GMT
References: <R73812w164w@mantis.co.uk> <30040@dime.cs.umass.edu> <1991May4.192440.5527@sctc.com>
Sender: news@chaph.usc.edu
Organization: Free Roger Carasso!
Lines: 47
Nntp-Posting-Host: alcor.usc.edu

beede@sctc.com (Mike Beede) writes:
>yodaiken@chelm.cs.umass.edu (victor yodaiken) writes:

>>The halting problem does not really apply to actual programming languages
>>(i.e. those that are compiled or interpreted into machine code).
>>The sooner computer scientists begin to understand the actual meaning
>>of the undecidability and complexity results, the better off the filed
>>will be.
>
>Trivially, this is true.  We can always run the program on the machine
>and look for a cycle in the total state (all memory, all register, all
>etc.)  Then we wait for on the order of 
>
>	2 ^ ( 2 ^ wordsize * ( memorysize + registercount ) ) 
>
>cycles (corrected for any non-binarity of the machine) and if we don't
>get a repeat, the program never halts.

This wouldn't work even if you did have more than all the time in the
universe.  If the program does any file I/O, you have to examine
the state of the external store.  If it does terminal or network I/O,
this algorithm doesn't even apply.

I have to agree that the halting problem doesn't apply to 
real computer programs, though.  Many programs aren't 
*supposed* to halt on every input (interactive processes,
network servers, etc.; these act like finite state transducers
and theoretically *should* be able to run forever.)
Most programs alternate between doing some I/O and doing some
computation.  The "doing some computation" part is what 
we'd like to solve the Halting Problem for.  Theory says
that we can't write a program that will correctly answer
"yes" or "no" to the question "will this procedure halt on 
all inputs?"  but if we allow it to answer "I can't tell," 
it becomes entirely possible.  If the algorithm were smart enough,
this might even be a useful tool for a limited class 
of procedures.

Of course, since we know the HP is insoluble, that's a 
pretty strong hint that the algorithm would have to 
be pretty smart to not anwer "I can't tell" on all but
the most trivial procedures, but it isn't impossible.


--Joe English

  jeenglis@alcor.usc.edu