🚀 go-pugleaf

In article <30082@dime.cs.umass.edu> 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).
->
->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. 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. 

This thread began when someone mentioned the relationship between strong
typing and the problem of deciding whether a given function specifies a
terminating computation.  In this context, "termination" is generally 
understood to be a property of the algorithm (and perhaps its input), NOT
the machine used to run the algorithm.   Your formulation requires us
to tie the definition of "terminating" to a specific compiler and machine
configuration (including the amount of off-line storage available for the
computation).   It's about as useful and interesting as saying that
"Fermat's conjecture is true (in BASIC on a TRS-80 with 4k of memory...)"

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

It is also the case that there is no general algorithm to solve the
halting problem for *any* universal TM.  And decision procedures
for the halting problem on non-universal TM's (e.g. the ones that
are equivalent to FSMs) usually aren't very interesting, because they
don't tell you what happens if you throw a bigger state space at the
problem.

->>The sooner computer scientists begin to understand the actual meaning
->>of the undecidability and complexity results, the better off the filed
->>will be.

On behalf of computer scientists everywhere, "Eat my shorts!" :-)

-- Jim Lewis
   U.C. Berkeley