3 ms·
But wouldn't that require additional instructions to exchange values between the two stacks? Otherwise you'd basically just run two independent programs at the
by alpaca128 6y ago
But wouldn't that require additional instructions to exchange values between the two stacks? Otherwise you'd basically just run two independent programs at the same time. In theory you could just replace a single letter's functionality with "push first element to other stack". v and w are redundant, for example.
- lifthrasiir 6y agoYou can put only ones and zeros to two stacks and branch against one stack to manipulate another stack. This is enough for simulating a two-symbol tape and thus any TM operating on that tape.