“Every language accepted by a multi tape Turing Machine is recursively enumerable” – Explain.

Proof: Suppose language L is accepted by a k-tape TM M. We simulate M with a one-tape TM N whose tape we think of as having 2k tracks. Half these tracks hold the tapes of M, and the other half of the tracks each hold only a single marker that indicates where the head for the corresponding tape of M is currently located. Figure assumes K = 2. The second and fourth tracks hold the contents of the first and second tapes of M, track 1 holds the position of the head of tape 1 and track 3 holds the position of the second tape head.

Figure: Simulation of a two-tape Turing machine by a one-tape Turing machine.

To simulate a move of M, N’s head must visit the K head markers. So that N not get lost, it must remember how many head markers are to its left at all times; that count is stored as a component of N’s finite control. After visiting each head marker and storing the scanned symbol in a component of its finite control, N knows what tape symbols are being scanned by each of M’s heads. N also knows the state of M, which it stores in N’s own finite control. Thus, N knows what move M will make.

N now revisits each of the head markers on its tape, changes the symbol in the track representing the corresponding tapes of M, and moves the head markers left or right, if necessary. Finally, N changes the state of M as recorded in its own finite control. At this point, N has simulated one move of M.

We select as N’s accepting states all those states that record M’s state as one of the accepting states of M. Thus, whenever the simulated M accepts, N also accepts and M does not accept otherwise.