🚀 go-pugleaf

yodaiken@chelm.cs.umass.edu (victor yodaiken) writes:

>In article <truesdel.673301155@sun418> truesdel@nas.nasa.gov (David A. Truesdell) writes:
>>yodaiken@chelm.cs.umass.edu (victor yodaiken) writes:
>>
>>>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.

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

Wrong!  Last time I looked, a Turing machine consisted of a finite state
machine and an infinitely large memory.  "Real computers" really differ only
in that they have a finite amount of memory.

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

Of course you leave "reasonable" undefined. :-)  Other than that, it seems
that the since the halting problem doesn't "interest" you, it isn't important.
You sound like a typical academic.

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

I'd guess your definition of "interesting" probably means "trivial".

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

Beware, problems of "theoretical interest only" have this nasty habit of
sneaking up and biting you on the ass.

--
T.T.F.N.,
dave truesdell (truesdel@nas.nasa.gov)
'And Ritchie said, "Let there be portability!"  And nothing happened, so
 Ritchie realized that he had his work cut out for him.'