Re: on formally describable universes and measures

From: <juergen.domain.name.hidden>
Date: Wed, 3 Jan 2001 16:01:33 +0100

On Thu Dec 28 05:19:13 2000 Wei Dai wrote:
>I think we understand each other sufficiently on the other issues, so I'll
>only follow up on this one. I agree that our universe can be simulated on
>a classic TM. What I don't agree with is that our universe can be
>simulated quickly on a classic TM, which is what a speed prior based on a
>classic TM would predict. In other words, the speed prior predicts that we
>will never observe any quantum effects that can't be simulated quickly on
>a classic TM. I suggest that you talk about this prediction more
>explicitly in your paper since it would have major consequences. Many
>people are busy trying to build quantum computers, which would be a waste
>of effort if this prediction is correct.

I agree; probably one should say a bit more about these somewhat
discouraging consequences.

>Even within classic models of computation, there seem to be significant
>variations in speed. As far as I can tell from my theory of computation
>book, moving from a multi-tape TM to a single-tape TM can cause a squaring
>of running time for some problems, which would translate to a squaring of
>the speed prior for some strings. So a similar question is, how do you
>pick which classic TM to base S on?

Good point. Simulating a k-tape TM on a 1-tape TM may cause a quadratic
slowdown indeed. Simulating a k-tape TM on a 2-tape TM, however, causes
at most logarithmic slowdown. One should use a TM with several work tapes.

Juergen
Received on Wed Jan 03 2001 - 07:06:29 PST