Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!uwm.edu!uwvax!daffy!saavik.cs.wisc.edu!quale
From: quale@saavik.cs.wisc.edu (Douglas E. Quale)
Newsgroups: comp.lang.misc
Subject: Re: The Halting Problem is _not_ solvable on real com
Message-ID: <1991May15.145359.20719@daffy.cs.wisc.edu>
Date: 15 May 91 14:53:59 GMT
References: <3125@cirrusl.UUCP> <3069@optima.cs.arizona.edu> <30505@dime.cs.umass.edu>
Sender: news@daffy.cs.wisc.edu (The News)
Organization: University of Wisconsin -- Madison
Lines: 48

An earlier poster said that thinking of computers as analog devices is not
a very useful view of computation.  This is true.  The problem is that the
operation of a real computer is not the same as our abstract notion of
computation.  When considering real machines at lower and lower levels of
abstraction eventually statistics enters in and we lose determinacy.

In arguing that an FSM is a more appropriate abstraction than a TM for
modelling execution of a program on a real computer, three points come
to mind:

1) Undoubtedly sometimes an FSM is more appropriate, but

2) The FSM view ties us to a particular machine.  I don't think this is a
   very useful view of computation. :-)  Generally we want our  programs
   to behave similarly on different machines.  I want to say "This program
   will terminate with result foo or with an error condition if not enough
   memory is available."  I don't want to say "This program will terminate
   with result foo if run on a small enough machine but I don't know what
   it will do otherwise."

3) When considering termination, an FSM has only two posssible behaviors
   on any given input:  termination or infinite loop.  A TM can terminate or
   it can fail to terminate either by entering an infinite loop or by simply
   running forever never repeating any earlier state.  Since most programming
   languages do not specify that they must be run on a finite machine we can
   consider these programs as FSMs on a finite machine or as TMs on an
   infinite machine.  Now, the 64K question is:

* What useful programs terminate as FSMs and fail to terminate as TMs?

   The most obvious example is a memory testing program, but I think that
   nearly all programs that terminate only on FSMs are bugged or useless.
   It would be very interesting, however, to have you folks think up a
   bunch of useful programs to prove me wrong.  In general it seems to me
   that having to resort to finiteness of the machine to prove termination
   is a sign that something is wrong (unless we are considering the
   memory test).

(In an earlier post I referred to the Goldbach Conjecture as the Goldbach
hypothesis.  My apology for the blunder.)
If the halting problem were solvable, then it could be used to decide any
mathematical problem involving only a countably infinite number of test
cases.  In addition to Fermat's Last Theorem, the Riemann Hypothesis and
Goldbach's Conjecture, I'd like to know whether or not there are any odd
perfect numbers....

-- Doug Quale
quale@saavik.cs.wisc.edu