🚀 go-pugleaf

In article <truesdel.673301155@sun418> truesdel@nas.nasa.gov (David A. Truesdell) writes:
>yodaiken@chelm.cs.umass.edu (victor yodaiken) writes:
>
>>>Last I heard, the Halting Problem was still insoluble.
>>>
>>>Is there some new theoretical result you'd like to share with us?
>
>>The halting problem does not really apply to actual programming languages
>>(i.e. those that are compiled or interpreted into machine code).
>>The sooner computer scientists begin to understand the actual meaning
>>of the undecidability and complexity results, the better off the filed
>>will be.
>
>Care to share the reason why the halting problem does not apply?  Or, is
>this just some handwaving by someone who really doesn't understand what the
>halting problem means.
>--
>T.T.F.N.,
>dave truesdell (truesdel@nas.nasa.gov)

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 
language L and an algorithm C that will transform programs over
L into machine language for a reasonable computing device, then
C transforms L programs into finite state machines.  In these
situations, the pumping lemma is of far more interest than the 
halting problem. To suggest that type checking a compilable
language is impossible because of the Turing theorem is to misapply
the Turing theorem.  In fact, even if we were to ignore the fundamental
boundedness of actual computing devices, we would be wise to 
apply Turings theorem very cautiously. It is well known that there is no
decision method for arithmetic, but number theorists don't seem to 
be too crippled by this situation. Turing showed that there was
*no general algorithm* that would solve the halting problem for all
turing machines. This does not mean that there is no algorithm for
solving the halting problem for all interesting cases. Turing's
result should be of interest primarily to meta-mathematicians and
logicians. Those concerned with applied mathematics, and programming
languages certainly seems applied, don't really have to worry about it.