A difficulty in understanding The implementation level description of a multi tape TM.

200 Views Asked by At

I could not understand exactly what this implementation level description mean:

enter image description here enter image description here

Could anyone explain an example to me that clarify it please?

1

There are 1 best solutions below

0
On BEST ANSWER

To put multiple tapes on a single unified tape, write the following on the unified tape:

  • List the current contents of the tapes in order and put a dividing symbol $\mathtt{\#}$ between them so you know where the contents of each tape begin and end.
  • Each of the tapes has its own TM head, so use a marker decoration $\dot{}$ to mark the cell where the TM's head is supposed to be on that tape.

Now you can simulate moving the head left and right on each of the tapes separately (just erase the "head marking" dot and move it to the left or right.)

The virtual tapes are supposed to seem infinite, even though you've only allocated finite space to them with $\texttt{#}$ divider symbols in between. If you ever move past the end of the allocated space (i.e. you reach a divider symbol), you can always create some more space: to make more space on the right of the current position, just shift all those symbols one step rightward.