I don't think it should because a third stack would be superfluous. The machine could just reuse the first stack after it uses the second right?
I'm just beginning to learn about Turing machines, so any help appreciated!
I don't think it should because a third stack would be superfluous. The machine could just reuse the first stack after it uses the second right?
I'm just beginning to learn about Turing machines, so any help appreciated!
Here's a straightforwardly boring way to see why a three-tape and one-tape machine are the same:
Maybe a clearer way to say it is that you can simulate a one-tape TM on a three-tape TM (use one of the three tapes to write down the current state of the simulated one-tape TM). You can also, maybe surprisingly, simulate a $k$-tape TM using only a one-tape TM. (The trick is that at any given moment, the $k$ tapes only have finite amounts of information on them, so you can write that all down on a single tape with $\mathtt{\#}$ symbols to separate the contents of different tapes, and dots to indicate where the $k$ tape-heads are located.) This means that a $k$-tape machine and a one-tape machine are equivalent.