From: Robin Lee Powell (rlpowell@digitalkingdom.org)
Date: Tue Oct 13 2009 - 11:37:13 MDT
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
-- They say: "The first AIs will be built by the military as weapons." And I'm thinking: "Does it even occur to you to try for something other than the default outcome?" See http://shrunklink.com/cdiz http://www.digitalkingdom.org/~rlpowell/ *** http://www.lojban.org/
This archive was generated by hypermail 2.1.5 : Wed Jul 17 2013 - 04:01:04 MDT