3 ms·
That's fair. I only mentioned it because you asked for a computer scientist. One simple model of a parallel Turing machine is one with multiple tapes, each wit
by daveFNbuck 8y ago
That's fair. I only mentioned it because you asked for a computer scientist.
One simple model of a parallel Turing machine is one with multiple tapes, each with its own read-write head. They all operate simultaneously based on the global state. This is a very general form of parallelism.
Wikipedia has an article [1] about them with some references for proofs that they're equivalent to single-tape Turing machines, but I encourage you to try to prove it yourself. It's fairly simple to prove, I'm pretty sure I've seen it as an undergraduate-level homework problem.
If you want a hint, try increasing the number of tape symbols so that you can encode the entire global state on one cell of the single-tape machine. It's a bit more work, but you can also show that two symbols are enough to simulate a Turing machine with any number of symbols.
[1] https://en.wikipedia.org/wiki/Multitape_Turing_machine https://en.wikipedia.org/wiki/Multitape_Turing_machine
- daveFNbuck 8y agoThe proof is a little trickier than I remembered. There's a bit more housekeeping to handle that each head can be on a different cell of their respective tapes. Try coming up for a proof for the case where each head moves in the same direction so they're always all on the same position of their tapes first. This can be extended to the general case by some annoying bookkeeping.