🚀 go-pugleaf

Victor Yodaiken:

   The kind of looping that makes Turing machines undecidable is quite
   different from the kind of looping we get in real machines. On a
   turing machine
	       while(true)i = i+1;
   is a truly infinite loop, each iteration takes us to a new state.
   But on a real computer,
	       while(true)i = i+1;
   *will* repeat state (or crash the program). Here we have a *finite*
   loop.

er.. I hate to say this, but (brought to you through sheer brute effort): 

Assuming I agree with you, so what?


First off, a loop of the form   while(true) i=i+1   implemented on a
turing machine is NOT what make the turing machine undecidable.  (In
fact, it is trivial to determine if that loop halts:  if the machine
is using arbitrary precision arithmetic, it won't halt.  if the
machine is using a finite state arithmetic it will or won't halt
depending on how the overflow condition is defined).

What makes turing machines undecidable (to gloss over all the details)
is that you can write programs of arbitrary complexity.  (NOTE: not
infinite complexity, arbitrary complexity -- circularly defined for
the purposes of this article as complexity sufficient to be
undecidable that some program H can not determine if this complex
program halts.)

Second off, all I said was that unbounded loops and recursion must be
eliminated.  I carefully did not describe any specific mechanism for
doing so.  If your recognizer can determine that   while(true) i=i+1
will halt on your system, then it is fine to include it.  The key here
is to eliminate any ambiguous cases.  A simple example of which is
while(true) i = f(i)    :-).  Personally though, I wouldn't bother
considering this case as a halting case (why bother)?

Anyways, if your point is that for a finite state machine with n
states, a table with n entries is going to be able to list whether
each state halts, I understand the concept.  Or, if your point was
that a binary machine capable of representing at most n bits of
information has at most 2^n states, then yes I understand that too.
Thank you for pointing it out.

Raul Rockwell