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

On Mon, Sep 20, 2004 at 11:45:18AM -0400, Daniel Martin wrote:
> 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.
> 

This is only for debuging the turing program and would be a command line
argument.


Ned