Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!dali.cs.montana.edu!uakari.primate.wisc.edu!sdd.hp.com!samsung!transfer!lectroid!jjmhome!smds!sw
From: sw@smds.UUCP (Stephen E. Witham)
Newsgroups: comp.lang.misc
Subject: Re: The Halting Problem is _not_ solvable on real com
Summary: FINITE STATES DOESN'T MEAN MODULO ARITHMETIC!
Message-ID: <472@smds.UUCP>
Date: 17 May 91 16:25:56 GMT
References: <3069@optima.cs.arizona.edu> <30505@dime.cs.umass.edu> <30581@dime.cs.umass.edu>
Organization: SMDS Inc., Concord, MA
Lines: 45

In article <30581@dime.cs.umass.edu>, yodaiken@chelm.cs.umass.edu (victor yodaiken) writes:
> [some reasonable stuff...]
> 
> n = m*m
>          does the multiplication on a TM, may compute  m*m MOD k
>          on a FSM

If so, it's because of the compiler, not the machine itself.
You can compile a program for a regular computer so that the program 
either computes to whatever precision is needed, or quits.

So there are two issues you're mixing here:
   1) What if the compiler in one machine thinks arithmetic is to be
      done modulo some word size?  I.e., what if different compilers
      interpret the same program TEXT differently, resulting in
      DIFFERENT PROGRAMS, and
   2) What if you know that all your compilers agree exactly on the
      meaning of the text, so all your computers are running the SAME 
      PROGRAM, but some of them can't keep running it if it needs too
      much memory?

As far as the halting problem per se, on FSMs per se, only question 2 
makes much sense.

> [...more examples, some reasonable...]
> 
> 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.

Fixed-size representations of numbers are not an inherent limitation of
computers!  They are just a convenience, too.  Thinking that integer 
variables behave like integers only leads to errors IF you're using a 
compiler (or a method of programming) that doesn't treat them that way.

You are obviously aware of the limits of correctness in the programming
context you're used to, but you seem almost unaware that there are
other ways of doing things (and I do mean with real computers).  
Snap out of it, guy!  Was it a momentary lapse, or are the limits of your 
thinking really so tied to convention?

--Steve Witham, sw@smds.UUCP
Not-the-fault-of: SMDS, Inc., Concord, MA