On Thu Dec 28 05:19:13 2000 Wei Dai wrote: >>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? Juergen answered: >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. Talking about optimizing the universal Turing machine is completely ridiculous and pointless. It could be blindingly fast or slow as molasses. Since perceived time is relative to the observer it would not make a bit of difference. And BTW I do believe that engineering will drive philosophy by making quantum computers work. George
