[hudnqucv] Multi tape Turing machine

Augment a single tape Turing machine with an infinite number of additional tapes and two additional instructions: NextTape and PreviousTape, which transfer the read-write head to an adjacent infinite tape.  It's kind of like a single-tape Turing machine where each tape cell itself is an infinite tape.

Each tape maintains state of where the head was when it leaves, and restores that position when the head returns.  This is probably easy to simulate and implement using a lazy list of lists in Haskell.

The motivation for this augmentation is to make programming on the Turing machine more convenient.  The multiple tapes could be used like registers. It is backward compatible with a single tape machine, as a single tape program simply does not use the extra instructions.  (It is also "forward-compatible" by the famous theorem that a single tape Turing machine can simulate any reasonable model of computation.) This machine could be nicely depicted on a 2D display, where the tapes slide, and the head remains at the center of the screen.

Next, given the above mentioned view of a tape of tapes, recurse again to get a tape of tapes of tapes.  Recurse an infinite number of times.   How would you program such a thing?

Transfering control to a different tape would take many steps, utilizing a sequence of the instructions Higher, Lower, Left, and Right, like navigating a tree (but where every node has an infinite number of siblings, and there is no root: it's turtles all the way up).  The "NextTape" command on the two-level machine would now be Higher, Left, Lower.  Is there any convenience advantage over the two level tapes?

Organizing data into a tree means arbitrary memory locations can be accessed in logarithmic time, instead of linear.

I believe this could be simulated in Haskell with a zipper on a tree, each node whose context is a lazy infinite data structure.

Update:

An implementation in Haskell. This is one of those things that are fun and elegant to implement in Haskell. (Lazy) Infinite in all possible directions.

Also explored the idea that the head can write any of three symbols on a tape: False (blank), True, and a recursive infinite blank tape, to which the head can descend down. The head may also ascend upwards forever, each time encountering blanks to the left and right, and an infinite subtape underneath the head from which it just ascended.