Please enable JavaScript.
Coggle requires JavaScript to display documents.
TOC Week 6, Converting between a fancy TM and an ordinary TM, A polynomial…
TOC Week 6
2) Give a "Setting-up" program to convert the initial configuration into a corresponding one for the simple TM
-
We add one character at a time - move down every character after the current head position to add a space and replace the space with the appropriate character
-
-
-
3) For each instruction of the fancy TM, show how to perform it on a simple TM
We simulate each instruction by a program of the simple TM (usually involving an extra step for each original step so a ten step program becomes 20 or more)
-
In general, the worst case space efficiency is proportional to the execution time or less
e.g. if we have time complexity of 100 steps, the maximum space complexity is the space complexity to begin with plus 100
We can do the same thing for 2D Turing Machines, using T and B for to enclose the entire statement to show the top and bottom row we're representing
-
We add additional "head" positions where we define whether the head is at this position and the two tapes are alternated because each has the opportunity to be too long to go back and forth over without having too large of a time complexity
-
-
-