Re: being inside a universe

From: Bruno Marchal <marchal.domain.name.hidden>
Date: Fri, 5 Jul 2002 20:25:31 +0200

Hal Finney wrote:



>Yes, I meant a constant additive term. Any UTM can emulate any other
>TM using a fixed size prefix in front of the other TM's input tape.
>(This assumes that the two TMs use the same basic alphabet of characters
>for their input tape.)

OK. That follows from Church Thesis.



>
>However I may have been too general in making this assertion about all
>universal computers (a larger set than UTMs). It's possible that some
>UC's would need to scale the size of the program in order to emulate
>others, so in those cases it is not just a fixed additive term. I would
>have to look more closely at other models of universal computation to
>get a better understanding of this point.


Church thesis is equivalent to assert that a UTM, or JAVA, lambda,
... including Deutsch Universal Quantum Turing Machine, ... can
emulate each other.
All those thesis are provably equivalent, giving an empirical evidence
that "computability" is sort of large invariant for combinatorial finite
digitilizable open manipulations. Open means *hopefully* capable of
getting more memory, (qu)bytes.

Quantum computing has demolished a weaker thesis saying that UTM can
simulate each other with slow-down/speed-up polynomial delay.

Church thesis is, imo, independent from what I would like to call
Deutsch thesis, which is that a QUTM (and thus a UTM) can simulate
all physical phenomena.

There is a paper by Freedman making seemingly possible some sort
of analogical universal machine which could beat UTM. But that "physical
phenomena" are capable of more than computing is almost "trivial"
for the computationalist which expect even white rabbits and
white noise a priori.

Perhaps I should recall that comp, as I have always presented, is
the hypothesis that "we" (whatever that means) are turing emulable.
It is not the more schmidhuberian hypothesis that
    1) there is a physical universe (but what's that exactly?)
    2) That universe is Turing emulable.

Quite the contrary if *we* are turing emulable then from our
inside view we have reasons for expecting trace of
non computationnal features with respect with our most probable
neighborhood. If we look below our "functionnal substitution
description" level, we should "see" (and share) trace of the
computationnal indeterminacy.

Now, a priori, this does not entail at all there exists a universal
analogical machine, and Freedman machine is intringuing. So I am
motivated for Chern Simons theory and topological field theories and
(not less fascinating fact!) how and why knots does help on the path.
You can guess that, for me, the question is: does such analogical
universal beast lives in some Z1* models?


M. Freedman. P/NP, and the quantum field computer.
Proc. Nat. Ac. Sci. USA, 95 (1998), 98--101.
You should find it on the net.
Received on Fri Jul 05 2002 - 11:22:38 PDT