Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!usc!elroy.jpl.nasa.gov!ncar!midway!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: <1991May16.140206.24573@daffy.cs.wisc.edu>
Date: 16 May 91 14:02:06 GMT
References: <30505@dime.cs.umass.edu> <1991May15.145359.20719@daffy.cs.wisc.edu> <30581@dime.cs.umass.edu>
Sender: news@daffy.cs.wisc.edu (The News)
Organization: University of Wisconsin -- Madison
Lines: 63

In article <30581@dime.cs.umass.edu> yodaiken@chelm.cs.umass.edu (victor yodaiken) writes:
>In article <1991May15.145359.20719@daffy.cs.wisc.edu> quale@saavik.cs.wisc.edu (Douglas E. Quale) writes:
>>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."
>
>I don't understand your reasoning here. Knowing that the state machine
>has a bounded number of states does not commit us to exactly what that
>number is.
>

Yes, but why do you want to write programs whose behavior depends on how
large a machine they are run on?  The behavior of your programs cannot be
determined without knowing exactly what that number is.  It is rather
difficult to say much about a program when its behavior is different on
nearly every machine.

>>* What useful programs terminate as FSMs and fail to terminate as TMs?
>
>Here are some programs that differ in interesting ways on FSMs and TMs
>
>while(true){ print(i), i = i+1 }
>      
>          loops or dies on a FSM, runs without repeating state on a TM
>
>
>i = 1
>while(i != 0) i = i+ 1
>
>          terminates with most definitions of FSM arithmetic,
>          does not terminate on a TM.
>
>
>
>Correct programs on real machines must respect that inherent limitations of
>digital computing devices.  While it is sometimes convenient to act as 
>if we were writing programs within an unbounded domain, e.g. as if
>"i" could indeed range over the integers, this is only a convenience
>when it does not lead to errors.

These programs are excellent examples because neither one is in the
slightest bit interesting.  Explain to me what useful programs contain
either of those fragments.  They look like bugs to me, unless you really
want an integer overflow or infinite loop with undefined results.  The same
remark applies to the other fragments you gave.

The question remains:
What program has an interesting result on an FSM and fails to halt on a TM.

It's important to remember that an TM program and input that terminates 
will use only a finite amount of tape.  If we restrict our attention to TMs
that terminate, we will have a class that could be run on real machines,
modulo space requirements.  (A TM isn't meant to model resource usage, but
an FSM is a pretty poor model for that purpose as well.)  The problem is that
we have no way to know whether a given TM halts.  To be safe, I would limit
myself to TMs that I could prove to halt, but we are forever undecided....

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