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?

  • 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

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.

| cite | improve this answer | |
  • $\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.