🚀 go-pugleaf

In article <1991May5.135342.13792@daffy.cs.wisc.edu> quale@khan.cs.wisc.edu (Douglas E. Quale) writes:
>In article <30082@dime.cs.umass.edu> yodaiken@chelm.cs.umass.edu (victor yodaiken) writes:
>>
>>Real computers correspond to finite state machines not turing machines,
>>thus the halting problem is trivially (in theory of course, not in
>>practice) solvable for real computers. If you provide a formal 
>
>and later
>
>>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.