Question

A beginner's question about "fine-grained" computational power.
Let $M_k$ be a $k$-tapes turing machine, and let $M$ be a single tape turing machine. We know that $M_k$ and $M$ both have the same "computable power". In addition, one can simulate $M_k$ on $M$ in a way that every computation which takes $O(t(n))$ on $M_k$ will take $O(t(n) \log(t(n))$ on $M$.
Here is my question:
Is there a language $L$ such that $L$ can be decided in $O(n)$ time in $k$-tape Turing machine (for fixed $k$, say 2), but can't be decided in $O(n)$ time in a single tape machine? (every single tape machine which decides $L$ needs $\Omega(n \log n)$ time).
In addition, are there any examples of two computational models (classical, not the quantum model) with the same computable power, but with fine-grained differences in their running time? (I guess that major changes in running time would contradict the extended Church-Turing thesis, which is less likely).

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top