Is Turing machine is robust ? if it solved with one tape, can it solved with multi-tape? I know that TM is robust but i can't understand why

  • 2
    $\begingroup$ This is classical material, which is described in textbooks. $\endgroup$ – Yuval Filmus Apr 11 '18 at 22:31

If you can solve it with one tape, you can solve it with multiple tapes by just ignoring all but the first tape.

The other direction is covered by Universal simulation of Turing machines.


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.