Re: [SPOILER] Perl Quiz of the Week #24 (Turing Machine simulation)

Ned D Hanks wrote:

> I am going to add some way of stopping infinite loops.  I was
> thinking of a counter per program line and an overall program
> counter.  The per line counter would get reset on a "state/tape
> value" change.

You do realize, don't you, that in the general case this is impossible
to do?  (That is, to have a Turing machine implementation that never 
continues forever, but rather halts if the program would go on forever) 
See http://en.wikipedia.org/wiki/Halting_problem

I don't doubt that there are special classes of infinite loops which you 
can build in code to handle.  And some sort of detection of the case:

    state _ state X R

when the tape is blank to the right of the head would probably be 
useful.  (And likewise for the left side)  But for whatever 
infinite-run-detection code you add, I guarantee either that there's a 
Turing Machine program that would halt but is erroneously detected as 
being stuck in an infinte loop by your code or that there's a program 
that will run forever undetected.  I'd also wager that the people on 
this list will be able to write such a counterexample to any 
infinte-loop-detection code in short order.