2
$\begingroup$

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).

$\endgroup$
2
$\begingroup$

The language of all palindromes needs quadratic time on a single-tape Turing machine. See for example lecture notes of Eric Ruppert. The proof uses crossing sequences. In contrast, on a two-tape Turing machine, the language can be decided in linear time.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.