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
