The tag has no wiki summary.

learn more… | top users | synonyms

1
vote
0answers
13 views

Multitape Turing machine with multiple non-blank tapes

A multitape Turing machine is defined to have input only appear on one tape, with the rest of the tapes blank. Are there any formulations of a Turing machine that allow other tapes to be not blank? ...
1
vote
0answers
69 views

K -> 2 tape reduction for nondeterministic Turing machines

How to I show that any language in NTIME(T(n)) can be accepted by a non-deterministic 2-tape O(T(n)) time-bounded Turing machine, with modifiable input tape? I've seen the k to 2 tape reduction for ...
1
vote
1answer
574 views

Multitape Turing machines against single tape Turing machines

Introduction: I recently learned that a multi-tape Turing Machine $\text{TM}_k$ is no more "powerful" than a single tape Turing machine $\text{TM}$. The proof that $\text{TM}_k \equiv \text{TM}$ is ...
4
votes
1answer
60 views

Why does it take $O(f(n)^2)$ to simulate a 3-tape $O(f(n))$-time TM on a 1-tape TM?

This looks like a fundamental result but I can't find a resource online that gives an intuitive interpretation of this complexity. Any basic explanation is appreciated.