Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!usc!samsung!crackers!m2c!risky.ecs.umass.edu!dime!chelm.cs.umass.edu!yodaiken
From: yodaiken@chelm.cs.umass.edu (victor yodaiken)
Newsgroups: comp.lang.misc
Subject: Re: Halting Problem Solved! Film at 11! (Was Re: definitions)
Message-ID: <30562@dime.cs.umass.edu>
Date: 15 May 91 12:26:23 GMT
References: <1991May5.135342.13792@daffy.cs.wisc.edu> <30164@dime.cs.umass.edu> <1991May13.055104.11872@daffy.cs.wisc.edu>
Sender: news@dime.cs.umass.edu
Organization: University of Massachusetts, Amherst
Lines: 77

In article <1991May13.055104.11872@daffy.cs.wisc.edu> quale@khan.cs.wisc.edu (Douglas E. Quale) writes:
>Real computers are *NOT* FSMs, and I hope most computer engineers are
>not surprised by this.  The rather small workstation on which I'm writing
>this is currently running about 34 asynchronous processes.  The next state
>of the machine depends very greatly on which key I strike next, the exact
>time at which I strike it, the exact current location of the 5 hard disks
>read and write heads, the value of all the peripheral devices hardware and
>hardware registers (many of which cannot be read by the CPU), and whether
>or not someone decides to log on to play Nethack.  (In fact, the state of
>the machine will be rather different if decides to play a priest rather
>than a knight, etc. ad. nauseum.)
>

Finite state machines are models of what happens when you hit the key.
A mathematical model that also predicted your behavior would be interesting,
but please try to remember the problem at hand.  The physical laws which
predict the path of a projectile in flight do not predict  whether or not
you will launch the projectile,  what the weather will be like, or whether
or not a bird will collide with the proejctile. Nevertheless, we find these
laws to be quite useful.

>This particular machine is fairly old and unreliable hardware.  Disk and
>other failures are rather common, and unpredictable.  Memory read and write
>errors are always possible, and they are not always corrected or even
>detected.  Via Ethernet, this machine is linked to dozens of others at the
>UW and literally tens or hundreds of thousands of machines on the Internet.
>The current state of this lowly workstation is dependent on the current state
>of all these machines.  The future state of this machine depends on what new
>machines will be linked to the Internet.
>

Again, you are arguing that the behavior of the people who manage the
Internet cannot be completely captured with a finite state machine. You
are correct. I doubt that a Turing machine provides a satsfactory model
either. Any machine model is defective according to this analysis. After
all, if someone shows up with a bag of chips and a soldering iron,they
can quite radically change machine behavior. Do we really need to model
all that?

>I completely disagree with you as to whether analog considerations are a
>useful way to think about computation.  It's essential to realize that our
>machines are not infallible, digital computation devices.  It's funny to
>see someone complain that TMs are an inappropriate abstraction for
>computation because they don't model real machines but that FSMs are -- and
>completely disregard the reality in real.


So, look at the analog behavior, look at the quantum level behavior, 
explain how brownian motion can alter the behavior of a Pascal program.
Please note, however, that TMs are just as discrete and deterministic
as FSMs. You seem to be arguing for a randomized non-linear differential
equation model of computation. Good luck.

>In regards to TMs and interesting problems,
>
>2) I won't speculate as to what the context of this group is, but of course
>you realize that a solution to halting problem would instantly provide the
>means to decide Fermat's last conjecture, the Goldberg hypothesis,
>Riemann's hypothesis etc.

Let's try to be a little more precise. The halting problem for *Turing
machines* is not Turing decidable. It is decidable by machines which can
complete infinite computation sequences. Similarly,  the halting
problem for FSMs is not decidable by any one universal FSM. It is, however,
decidable by Turing machines and even weaker machines such as LBAs. 

A Turing machine provides quite a useful model of constructive mathematics.
This is the intended purpose of Turing machines. Turing among others, 
wanted to provide formal definition for the intuitive mathematical notion
of "algorithm". Since, Turing's definition was intuitively acceptable
to many mathematicians, and since was shown to be equivalent to competing
definitions given by Godel, Church,Kleene, and Post, it has been
generally (but not universally, c.f. Bishop) accepted. 
Finding constructive proofs and algorithms in mathematics is very
interesting. But,  the existence or non-existence of a Turing computable
algorithm for a problem tells us little about what we can or cannot
do with actual computers.