Problem Idea Turing Machine 2D tape
Back to General discussions forum
In a course I took on Computational Complexity I recall one of the homework problems being to prove that a Turing Machine with a 2D tape can't do more than a standard TM, which simply involved showing how you could make a normal TM simulate a 2D Tape TM.
So, problem idea: you receive instructions to carry out on a 2D tape that you need to simulate with the normal 1D tape TM.
Sample input: URDDDLU0RRR1UUU0LLL1DDDPRURURUP
Resulting output: 00
URDL instructions correspond to Up, Right, Down, Left respectively on the 2D tape.
01 instructions tell you to store a 0 or 1 respectively
P instruction tells you to print out what value is stored in the cell you're currently on. X if nothing.
Vadim, Hi!
And thanks for sharing - as you may easily guess, most of us had no chance to take a course on computation complexityt to such depth at least :)
This seems to be related to your previous suggestion, with coordinates on spiral!
Probably it's time for me to try carefully understand how it is solved - perhaps this could be added quickly now :)
But then suggestion seemingly didn't involved real turing machine, only coordinates conversion...
Ah, that's what puzzles me: what do you mean by input for turing machine at all? Isn't the tape its input?
Ha, I see, I had already made a similar suggestion, I didn't realize. And yeah, this time we would be involving a real turing machine.
Yes, what I meant by Sample input for the turing machine is what would go onto the tape at the start of the turing machine's execution.
Small note, this should also be possible to do without doing this coordinate conversion, for instance you could maintain a map where the keys are coordinates and the values are whatever should be stored at that coordinate.
Well... Let me see... :)
So input is stored on the tape... And the goal is to make some movements on simulated 2D tape...
How do we make the problem of it, what is the output?
E.g. if it is just about printing out resulting coordinates, we do not need to do real movements on the tape, right?
Just need to perform calculations (though probably they are going to be weird/difficult with TM).
Other approach is that, for example, we require to visit the cells according this 2D-to-1D mapping and put some
marks in those cells. Then it is easy to check proper cells were marked - and thus, visited.
However this seems to be cumbersome with single-tape machine, right? We have movement commands at some place - and we need to make visits to other places, we need to run here and there all the time. And also, not sure, but feels like we need to keep a kind of "variable" for the coordinates or the size of spiral at current place... and this also needs to be stored somewhere on the tape...
It looks like the case when things are mathematically (theoretically) equivalent, but practically very different :(
So I think probably original idea should have some extensions to TM, some more powerful variation of it? Could you perhaps share the outline of implementation you keep in mind if you see I gravely misunderstood the suggestion?
As a practical example regard the task: on 2D tape there is a simple maze built of 0-s and 1-s. TM needs to traverse it (say between two positions specially marked) and mark the correct path (say, converting 1-s to 2-s). The TM operating on 2D tape would do this fairly easy (employing a kind of "keep-right-wall" algorithm) - but if we map the maze unto the 1D tape (for example using spiral coordinate conversion) - I guess I have no idea how the algorithm could be written (though probably it is possible to prove it could be written, though without indication how exactly).
BTW we really need to try creating some 2D TM tasks :)