Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!uakari.primate.wisc.edu!zazen!uwvax!daffy!khan.cs.wisc.edu!quale
From: quale@khan.cs.wisc.edu (Douglas E. Quale)
Newsgroups: comp.lang.misc
Subject: Re: Halting Problem Solved! Film at 11! (Was Re: definitions)
Message-ID: <1991May13.055104.11872@daffy.cs.wisc.edu>
Date: 13 May 91 05:51:04 GMT
References: <30082@dime.cs.umass.edu> <1991May5.135342.13792@daffy.cs.wisc.edu> <30164@dime.cs.umass.edu>
Sender: news@daffy.cs.wisc.edu (The News)
Organization: University of Wisconsin -- Madison
Lines: 74

In article <30164@dime.cs.umass.edu> yodaiken@chelm.cs.umass.edu (victor yodaiken) writes:
>In article <1991May5.135342.13792@daffy.cs.wisc.edu> quale@khan.cs.wisc.edu (Douglas E. Quale) writes:
>>>turing machines. This does not mean that there is no algorithm for
>>>solving the halting problem for all interesting cases. Turing's
>>
>>Naturally ``interesting'' is a subjective term, but I find the busy beaver
>>problem interesting, and it's unsolvable.
>>
>
>In the context of comp.lang.misc, the busy-beaver problem, whatever its
>intrinsic value, seems quite uninteresting. Diagonalization arguments
>are simply not the bread and butter of programming language design.
>
>>I should also point out that real computers are *not* finite state machines.
>>
>
>Pointing it out is nice, but most computer engineers would be surprised by
>this claim. If we build a device from 3dimensional switching elements, there
>are only two alternatives --- finite state device, or infinite volume device. 
>Of course, if we ignore the discrete nature of the switching elements and
>start worrying about analog behavior then things are different.  But, 
>this does not appear to be a very useful way of thinking about computation.

Someone posted earlier hitting some of what will follow, but I'll be
redundant anyway.

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.)

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.

1) Explain to me how this workstation qualifies to be called a deterministic
machine.

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.

When I asked a favorite math prof of mine what he disliked so about the
computer proof of the 4 color theorem he started by saying that the proof
was unsatisfying because he would naturally prefer a proof that he could
verify in his head, without relying on a machine.  His next statement
struck me more deeply; he stated that computer proofs are really proofs
consisting of an experiment in physics.  At first I thought this somewhat
silly, but I now understand that he was right.  Execution of a program on a
real machine is really nothing more than an experiment in physics.

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.

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