Re: Penrose vs the Robot


"abo" <dkfjdklj@xxxxxxxxx> wrote in message
news:1134109352.310287.266040@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
>
> Stephen Harris wrote:
>
> <snip>
>
> I was handwaving in what I thought was the spirit of your claim that
> any continuous process can be simulated by a discrete process. If a
> set is finite, then it is obviously recursive. If one supposes that
> every behaviour in the Universe can be represented by a finite set,
> then in some trivial sense it is computable; but not in any interesting
> sense (which I think is your point as well?).
>

Daryl wrote: "These three claims, which I think are both empirically
and theoretically justified, imply that we can't meaningfully
compute anything that isn't computable by a *finite* automaton.
The set of mathematical formulas that we can come to know
are valid is not only r.e., it is probably a regular expression,
or even a finite set."**

Here is David Chalmers musing on the possibilities (1989) and
doesn't seem to be conclusive.

"Basic question: is the universe an infinite-state-machine or a
finite-state-machine? **If the second, then it is WEAKER than a Turing
machine, so these analog solutions are essentially weak theoretically. If
the first, then is it true that it is STRONGER than a Turing machine? At the
very least, it seems that it has different theorems of computational
complexity.
The only way a Turing machine can accomodate 'parallelism' is through its
states. But as a TM has by definition only a finite number of states, then
indefinitely expanding parallelism is out of the question. (Of course, such
parallelism can be 'simulated' serially by use of its tape, but this is not
helpful for questions of computational complexity, although this is good
enough for questions of computability.)

If we have an infinite number of states, it seems that indefinitely
expanding parallelism can be accomodated. As we've seen, this leads to
better results for questions of computational complexity. It is an
interesting question whether such a machine was more powerful
computationally (in terms of the problems it could solve, independent of
resource-use).

Presumably we have to specify our definition a little better. First: do we
allow uncountable number of states? This might behave even better, but
presumably this is outside the spirit of computation, which has it that
algorithms must be well-defined and in a sense 'constructible'. The
well-known inconstructibility of uncountable sets (or at least of most of
their members) would seem to mean that such a machine is inherently
"impractical".

OK, given a countable number of states - we'll index them by the positive
integers. Next question: what do we allow as our transition functions? Do
they have to be computable functions, or do we allow any function Z x ... ->
Z to be 'hard-wired'. This question does not arise for finite-state
machines, because here any function is computable. My intuition here is that
again, to be computationally 'reasonable', such functions must be computable
and maybe even primitive recursive.

Incidentally, where does the physical universe fall into these classes?
Assuming it is (a) infinite and (b) discrete (this is arguable) then I
believe that, although the number of 'possible' states is uncountable (from
a calculation like 2-to-the-infinity), the number of 'reachable' states
(from constructible initial situations) is countable. And given that the
laws of physics are reasonable, the transition function is computable and
indeed primitive recursive (though it may be non-deterministic).

Finitely unbounded, Stephen




.