From: Stuart Armstrong (dragondreaming@googlemail.com)
Date: Tue Oct 13 2009 - 05:45:40 MDT
>> No. The algorithm that produces the digits of Pi is finite but it will
>> never return to its original state.
>>
>> John K Clark
>
> Oh, interesting. This points out an implicit assumption I was making,
> possibly incorrectly, about the meaning of "finite algorithm". I was
> imagining an algorithm running on a finite state machine whose size was
> fixed in advanced. You seem to be imagining a Turing-like machine with
> an indefinitely long tape that is finite at any given instant, but that
> grows as needed by the algorithm.
Even a Turing machine operating on a blank tape (all zeros), need not
return to the same state. Consider the following:
Turing machine A starts by moving left.
If it ever encounters a zero, it changes it into a one, and reverses
the direction of movement.
If it encounters a one, it keeps going.
This will simply cycle backwards and forwars on the tape, in ever
increasing periods.
This archive was generated by hypermail 2.1.5 : Wed Jul 17 2013 - 04:01:04 MDT