On Thu, Apr 17, 2008 at 2:34 PM, Eivind Eklund <eeklund / gmail.com> wrote:
>  My claim wasn't that reasoning about the system is not subject to
>  Goedel's incompleteness theorem - it is.

Ah, I see.

> It was that the properties
>  that was described as being a result of Goedel's incompleteness
>  theorem was in fact not related to that theorem.  That state proving
>  is impossible in the case of an infinite memory computer and often
>  infeasible the case of finite memory computers is, to the best of my
>  knowledge, a fully separate result.

I just looked up Wikipedia on the halting problem[1] - I quote:

"...any finite-state machine, if left completely to itself, will fall
eventually into a perfectly periodic repetitive pattern. The duration
of this repeating pattern cannot exceed the number of internal states
of the machine..."

which agrees with your statement, though the article continues:

Minsky warns us, however, that machines such as computers with e.g. a
million small parts, each with two states, will have on the order of
21,000,000 possible states:

    "This is a 1 followed by about three hundred thousand zeroes ...
Even if such a machine were to operate at the frequencies of cosmic
rays, the aeons of galactic evolution would be as nothing compared to
the time of a journey through such a cycle" (Minsky p. 25)

Minsky exhorts the reader to be suspicious -- although a machine may
be finite, and finite automata "have a number of theoretical
limitations":

    "...the magnitudes involved should lead one to suspect that
theorems and arguments based chiefly on the mere finiteness [of] the
state diagram may not carry a great deal of significance" (ibid).

When you consider that 1 million bits is about 128K, that is a sobering thought.

Regards,
Sean

[1] http://en.wikipedia.org/wiki/Halting_problem#Common_pitfalls