From: Charles Hixson (charleshixsn@earthlink.net)
Date: Tue Oct 13 2009 - 12:08:25 MDT
Robin Lee Powell wrote:
> On Tue, Oct 13, 2009 at 12:45:40PM +0100, Stuart Armstrong wrote:
>
>>>> 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.
>>
>
> The *turing machine* doesn't return to the same state, but the
> *algorithm* only has (I think) 3 states, so the algorithm returns to
> the same state routinely. Same with the Pi example. Program !=
> Data.
>
> The only way you can get a machine running deterministicaly that
> never returns to exactly the same state and never halts is if the
> program is infinite, or the data is infinite; the latter is the case
> of your Turing machine. On real computers, this isn't possible. So
> in fact what the person Stuart was replying to is correct, if you
> require both the FSM and the data to be finite.
>
> (Just to distinguish this from the rest of the discussion: I'm
> simply clarifying; no vitriol or arguing is intended).
>
> -Robin
Or if the data is occasionally altered by some external factor. E.g.,
if your memory isn't perfect, and occasionally does bit-flips (possibly
due to quantum processes).
OTOH, given that the program an the data is finite, there can be only
(#program states * #data states) states for the program (including
data) to be in. So the states would be recurrent. But a fallible
process might ensure that one couldn't predict with total certainty
which state would follow which other state.
Sorry, but this seems true from inspection.
Now consider that the observable universe is finite. Interpreting the
universe as a state machine, one can derive that it will eventually
enter a repeating set of states. If, of course, it lasts long enough.
So humans are contained within a machine that is finite. Therefore
humans are finite. Therefore humans (both individually and
collectively) can only think a finite number of thoughts. ----
Unless you postulate external factors. If you do, please be explicit
about this, and identify any constraints that you consider to exist on
those external factors. (No constraints is equivalent to unconstrained
magic. This is stronger than most gods.)
This archive was generated by hypermail 2.1.5 : Wed Jul 17 2013 - 04:01:04 MDT