1
$\begingroup$

This question already has an answer here:

I am studying the past exam paper of course Theory of Computation. I know it is always possible to convert a k-tape Turing machine to a single-tape one, but how will the running time complexity be changed?

$\endgroup$

marked as duplicate by Hendrik Jan, David Richerby, Rick Decker, Evil, Thomas Klimpel Oct 19 '16 at 7:42

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 4
    $\begingroup$ What are your thoughts? What have you tried? What's the fastest you can see how to achieve? Can you see how to do it with at most an exponential slowdown, and if so, what approach did you have in mind? We want to help you understand concepts, not do exercises for you. As you haven't shown us what steps you've taken on your own and haven't given us much to work with, it's hard to know how to help you. $\endgroup$ – D.W. Jun 14 '16 at 5:27
  • $\begingroup$ Are you aware of the fact that all (reasonable) Turing-complete formalisms can simulate each other with only polynomial overhead? $\endgroup$ – Raphael Jun 14 '16 at 9:35
0
$\begingroup$

It actually depends on the way you implement a k-tape Turing Machine as a single-tape one.

Using the standard implementation, you can prove that the single-tape machine will take quadratically more computation time.

$\endgroup$
  • $\begingroup$ What is the "standard" implementation? Can you provide any references? $\endgroup$ – Yuval Filmus Oct 13 '16 at 19:40

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