The 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.

The 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.