Re: Penrose vs the Robot


"abo" <dkfjdklj@xxxxxxxxx> wrote in message
news:1134117891.277546.11000@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
>
> Stephen Harris wrote:
>
>>
>> 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?
>
> I have difficulties accepting that this is an exhaustive choice, in the
> sense in which Chalmers probably means "machine" - as some kind of
> serial, deterministic thing.
>
>> **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.
>
> Well ok, but two Turing machines in parallel (which can communicate)
> are not equivalent to a (deterministic) Turing machine. Its behaviour
> can be (take your pick based on your preference) non-computable or
> non-deterministic, because what gets communicated depends on the timing
> behaviour of the two machines.

I didn't know that. A couple of related ideas I came across:
Theorem: Every nondeterministic TM has an equivalent deterministic TM.
A probabilistic TM is a nondeterministic TM where each nondeterministic step
has two legal next moves.


>
> (As some point Marvin Minsky will arrive and say, that's not true! and
> anyway we thought of that back in the 1950s!)
>

I mentioned that Deutsch tried to improve the Church-Turing Thesis
with something called the Church-Turing-(Deutsch) Principle. This ties
into Daryl's concluding remark: "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."**
-------------------------------------------------------------------
David Deutsch:
"I can now state the physical version of the Church-Turing principle:
"Every finitely realizable physical system can be perfectly simulated
by a universal model computing machine operating by finite means."
This formulation is both better defined and more physical than Turing's
own way of expressing it. (Deutsch 1985: 99.)"

SH: So the C-T Principle is popular among physicists but the concept
still appears to face a challenge judging by the dimensional remarks below.

-----------------------------------------------------------------------------
"Quantum mechanical measurements on a physical system are
represented by observables- Hermitian operators on the state
space of the observed system. It is an important question
whether all observables and all unitary evolutions may be
realized, in principle on physical systems [1]. It turns out
that ideas from computer science are crucial to the analysis.
The reason is that some problems that are classically considered
uncomputable can sometimes be recast as appropriate quantum
observables or unitary operations, which, if phyiscally
implementable, could apparently render them computable. There
has appeared to be no known principle that forbids the
implementation of such quantum mechanical observables or
unitary dynamics. If feasible, they would imply that quantum
mechanics not only impacts computational complexity, in terms
of speeding up certain computations [2], but also impacts
computability."
-------------------------------------------------------------------
info.phys.unm.edu/papers/1997/Nielsen1997a.ps.gz

"Natural processes may take place in infinite dimensional
state spaces, and it is has not been demonstrated that all
such processes can be well simulated using a system with
only a finite number of state space dimensions. Regardless
of whether quantum computers satisfy the Church-Turing
principle, it is certainly the case that the specification
of a universal model computing machine satisfying the
Church-Turing principle, besides being important in its
own right, would also greatly simplify the question of
characterizing the classes of measurements and dynamics
which are realizable in physical systems."

What is gained by using arguments based on the
Church-Turing principle instead of arguments based on
the Church-Turing thesis, is that it may be possible to
prove the Church-Turing principle within known physical
theory, for a suitable universal model computing machine.
Unfortunately, it is not clear to this author that the theory
of quantum computation (see [13{15] for a review), which
has developed from Deutsch's original proposal, provides
a candidate universal model computing machine. In particular,
it is not clear that the finite dimensional state spaces accessed
by quantum computers are sufficient to simulate, with
arbitrary accuracy, all the processes one finds in nature.
-------------------------------------------------------------


"The embedding in the Incompleteness Theorem is the same as the
encoding of Turing machines into input forms acceptable for
universal machines and is achieved by converting the finite
description of a Turing machine into a unique non-negative
integer which can then be expressed in binary or decimal or
any other convenient notation. The conversion is possible as
we are only dealing here with machines having a finite number
of states, a finite number of symbols in its alphabet, and
only a finite number of movements for their heads."

http://tph.tuwien.ac.at/~svozil/publ/ct.htm
SH: This is why you will see talk of the Zeno paradox. The
realm of the quantum state is infinite, but of course then
there is a collapse of the wave function or in any event the
next moment of physical reality manifests into finiteness.
Although it seems to me that this coalescing/actualization of
probability into reality is the state requiring the one-to-one
deterministic computation (computability).

arxiv.org/pdf/quant-ph/0203034
"Paradoxically, the quantum reality of Nature somehow allows us
to compress the infinitely incompressible randomness into the
apparently finite act of preparing the same quantum state over
and over again for subsequent measurements! This quantum
mechanically implied infinity seems to be both needed for and
consistent with the finitely measured, see [25] and references
therein for further discussion."
----------------------------------------------------------------

Peter Wegner: "Penrose argues that the nondeterminism of physics
may be illusory because physical phenomena maybe deterministic
but noncomputable. He ascribes the nondeterministic action at a
distance of the EPR experiment (section 5) to noncomputability of
physics and suggests that a noncomputable model of physics could potentially
resolve nondeterminism."
---------------------------------------------------------------------------
http://www.cs.nyu.edu/pipermail/fom/2000-August/004244.html
Similar ideas (C-T and computability have been discussed on FOM
which stands for Foundations of Mathematics under
"physical computability"

"Hello Stewart,

Joe and I (and some others) too are interested in this idea, that
uncomptable physical processes might occur in Nature (according to our "best
theory") and that by measuring the ouput, we get a physical reasons for
accepting mathematical facts independent of ZFC. It's not connected with
determinism (it might involve measuring the probabilistic statistics of some
quantum scattering experiment). And the issue of verifying the *theory* is
out of the question.

We accept the theory at face value. The theory says: there is a certain kind
of physical process P, and we can build a device M to generate this process,
and the output can be measured, and the output is an *uncomputable real*. We
then let it run - it produces a uncomputable ouput by this spooky physical
non-algorithmic process P. We humans (if what we can calculate is the same
as what some Turing machine can calculate) cannot "follow" this
computation - but it physically happens nonetheless, because that's how
Nature is built if the theory's right - and we can *measure* the result.

The theory states (in so many words) that the result is uncomputable (but
doesn't give a prescription for our computing it, a priori as it were).
Theories can *define* sets and quantities that are uncomputable (we can
define "theorem of PA" or "true sentence of lang of arithmetic" (in ACA
say), but Turing machines can't compute the characteristic function
involved).

Joe states (I've transcribed and removed the capitals):

>For any definable-but-not-recursive sequence a1, a2, a3, there is a finite
index N such that ZFC does not >decide the value of a_N; .... at some finite
time we will already have obtained a new mathematical fact >independent of
ZFC (but following from ZFC + T). This would demonstrate that mathematics is
not logically >prior to physics.

Sure - it's highly speculative, but it's a beautiful idea which I find very
attractive. It sheds quite a new light on Hilbert's optimism - his statement
"non ignorabimus" - that discovering new mathematical facts might involve
considerations from physical experiments.

Best wishes - Jeffrey Ketland"

SH: This mailing list includes contributions by Simpson and
Harvey Friedman and can be interesting reading. And it leaves
the subject somewhere in the territory of mathematical logic.

"This would demonstrate that mathematics is not logically >prior to physics"
Stephen


.

Relevant Pages

  • Quantum Computer Algorithms
    ... internal state (where these operations behave as in classical physics). ... time differed from computing device to computing device...) ... Our current best quantum mechanical ... which produce the same result as classical algorithms but ...
    (sci.physics.research)
  • Re: Symbol Grounding Problem (attn: Vend)
    ... For example, Physical CT covers operations on real-valued quantities, continuous dynamical processes operating on strings (as in certain kinds of connectionist computing and molecular computing), and quantum processes. ... brain over biological time. ... not make the physical system a Turing Machine. ... "e have good reason to believe that the laws of physics are computable, so that we at least ought to be able to simulate human behavior computationally." ...
    (comp.ai.philosophy)
  • Run this with A.I
    ... "If Numbers are Infinite, Then so Inventions" ... RESOURCE ACCESS CONTROL FACILITY IN PHYSICS, ... "Quantum chaos is real quantium computing!!" ...
    (comp.lang.prolog)
  • Run this with A.I
    ... "If Numbers are Infinite, Then so Inventions" ... RESOURCE ACCESS CONTROL FACILITY IN PHYSICS, ... "Quantum chaos is real quantium computing!!" ...
    (comp.lang.lisp)
  • Re: Can we get any quantum state from some classical state by unitary
    ... physics and I don't know whether my question is naive in physics. ... quantum computing, ... > classical state, and the unitary operator that will take you between ...
    (sci.physics.research)