4 ms·

Computability isn't really relevant here. I was talking about, for problems that are computable within NP, how big a problem can be solved by physically realiza

• lisper 6y ago
  > Turing machines are polynomially worse than von Neumann machines. No, they are not. > It'd be hard to factor 16-bit numbers on a physically realizable Turing machine, while we can do hundreds of bits on our laptops. Here you have done exactly what a prism does: put an upper bound on the problem size. When you do that, you can just precompute all the possible answers (because there are only a finite number of possible inputs) and the computation becomes O(1). To assess computational complexity you have to do it with respect to an unbounded input size. And when you do that, you will find than VNMs have only a constant advantage over TMs, not a polynomial one. This is because a VNM has a finite word size and so can only randomly address a finite memory, and so it can be emulated by a TM in constant time. There is no getting around this. Either you bound the input size or you don't. If you do, it's all O(1) which isn't very interesting. If you don't, all computational models are equivalent (except quantum computers, which give you an exponential speedup for some problems). This is the entire reason that computational complexity theory is interesting in the first place, because you can talk about it coherently without committing to a particular model of computation.