Problem Idea 1D tape simulating 2D tape
Back to General discussions forum
When I was taking a course on Computational Models, we had the following question appear on a Homework.
Consider a Turing Machine with a 2-dimensional tape. The head now has 4 possible moves, up, down, left, or right. (Everything else is to a standard Turing Machine.) Prove that a Turing Machine with a 2-dimensional tape can be simulated by a standard Turing Machine
A normal turing machine is only 1-dimensional and extends infinitely in either direction. A 2-dimensional turing tape is supposed to extend infinitely up,down,left,right.
Anyways, the key idea for showing how this could be done is basically summarized by this diagram
The problem statement I am imagining is this: We are given a Turing Machine that is only capable of increasing and decreasing it's index along a tape. We want to have this 1-dimensional Turing Machine simulate a 2-dimensional Turing Machine, so when it receives instructions to move up,down,left,or right, we have to tell the 1-dimensional turing machine how much to increase or decrease it's index. We can also assume that either the Turing machine will start at cell 0, or the starting cell could also be part of the input.
Assuming the machine starts at cell 0, and supposing we had the following test data:
U R U L L U U R U R D D L
The machine would visit these cells after executing each movement.
3 2 13 14 15 34 61 60 95 94 59 32 33
So the output of the program should be
3 -1 11 1 1 19 27 -1 35 -1 -35 -27 1
Also, another idea for a problem, that does something related to the above but adds a more complicated step. Based on this video: https://www.youtube.com/watch?v=3s7h2MHQtxc
The problem statement would be, given a list of floating point numbers, figure out which point each should map to when mapping it through the Hilbert curve function.
Also... the Hilbert curve appears to have a variety of applications in Computer Science: https://en.wikipedia.org/wiki/Hilbert_curve so an implementation of this can also be practically useful :P
Vadim, Hi!
Thanks for thorough explanation! I created issue #68 for now, so it's not lost while I'm pondering on it :)
This translation of coordinates seems to be pretty common (reminds me of Ulam's Spiral), but probably not very effective for real Turing machine! :)
I remember long ago trying to create 2D turing machine which had besides internal state also the direction and
besides step command could do right and left turns by 90 degrees. It was pretty easy to make it crawling over
2D maze, but I haven't invented other interesting applications...
figure out which point each should map to when mapping it through the Hilbert curve function
I vaguely heard of Hilbert's curve only... This can make brain jetting out of ears easily :) I'll try to figure out how do we solve this!