Register to reply 
Paper Tape Turing Machine 
Share this thread: 
#1
Apr2806, 04:16 PM

Sci Advisor
P: 1,253

This was a bonus problem that I missed on the last homework.
A paper tape Turing machine (PTM) is a Turing machine whose tape alphabet is partially ordered, and if a is a symbol on a square of the tape, then b can only be written on that square if b is greater than a in the partial order. Show that a PTM can simulate T steps (tape head movements/writes) of a onetape Turing machine in O(T^2) steps. O(T^3) is easy, you can just copy the whole tape over again at every step for O(T^2) PTM steps at step T of the TM. To get O(T^2) the PTM head can't move more than O(T) steps at a given step T of the TM, which means it can move back and forth over the PTM tape at most a constant number of times on average per step of the TM. When you need to change a symbol on a tape square in the wrong direction, the natural thing to do is go to the right or to the left until you have an empty square, and write the new symbol. If this could be made to work, it would be T^2 time. But I don't see how to maintain the association between the new symbol and the old square. 


#2
Apr2806, 05:13 PM

Emeritus
Sci Advisor
PF Gold
P: 16,092

Bleh, too many little details.
Are you trying to come up with a PTM that can simulate a specific TM, or are you looking for one that can simulate any TM that's given to it as input? Is the number of steps to simulate a parameter? Or is it just supposed to simulate indefinitely, but at any point in time the number of simulated steps T is less than cT² for some T? Or is T supposed to be the number of steps before the simulated TM halts? Are you allowed to choose the alphabet for your PTM? I suppose WLOG you can assume the TM alphabet is {0, 1}. Oh, I suspect that WLOG you can choose your alphabet for the PTM for the same reason you can assume the alphabet for your TM is {0, 1}. 


#3
Apr2806, 06:50 PM

Sci Advisor
P: 1,253

What the PTM must do is simulate a given TM. That is, given the Turing machine M, supply the PTM M' that can simulate the action of M on any input. You can pick your alphabets (so long as they are finite of course).
The problem didn't specifically say whether the TM halts at T steps and the PTM must take no more than cT^2 steps to output the same thing, or whether there must be some interpretation of the PTM's state after cT^2 steps that corresponds to T steps of the TM. I don't see a practical difference in terms of which interpretation is easier to solve since I don't see any way to mimic the TM's output behavior without mimicking the TM's tape step by step. 


#4
Apr2806, 10:29 PM

Emeritus
Sci Advisor
PF Gold
P: 16,092

Paper Tape Turing Machine
Or maybe you don't need to know it ahead of time; maybe you can simulate one step, then restart and simulate two steps, ... then restart and simulate 2^n steps, then ... 


#5
Apr2906, 08:50 AM

Sci Advisor
P: 1,253

I'm pretty sure you can't know T ahead of time, since if you knew T and you knew the machine, then your algorithm for constructing the PTM could just be "run the real TM for T steps and generate a PTM that writes exactly the TM's information on the tape" giving O(T) simulation time or even O(1) if you only care about output.
I don't think there's a lot you can do with the alphabet. The TM alphabets have to have more than one symbol and since the QTM has to simulate the TM, the input alphabet has to be the same. As you said any alphabet can be simulated by the alphabet {0. 1}. You can add delimeters and blackedout symbols as you need to. A trick I've seen in class is extending the tape alphabet from gamma to (gamma x gamma) or (gamma x gamma x gamma) etc. so that each tape square can hold an ordered ntuple. You can denote the virtual tape head location with an h symbol. Another way to denote the virtual tape head location is to have the tape squares hold an extra piece of data that says {0, 1} depending on whether the simulated tape head is on the square. One thing I was thinking about a little was that the squares could hold directional information, allowing you to maintain the necessary assocations between a square and its rewrite history. The squares could indicate something like, "go left until you find a square with a green mark." Then at the square with the green mark, you get another symbol telling you to "go right until you find the third square with a red mark." Then at the square with the red mark, you get another symbol telling you to "go left five squares," and five squares left of that you find your data. I haven't figured out just how that might work so that each square still only needs to store a finite amount of directional information to maintain associations between an unbounded number of squares. 


#6
May406, 05:21 PM

Sci Advisor
P: 1,253

The professor talked about the problem in class today. It turns out there was a mistake on the assignment and he really only meant the implementation had to be O(T^3).



#7
May406, 06:39 PM

Emeritus
Sci Advisor
PF Gold
P: 16,092

That doesn't mean it's still fun to work on it. If we can't prove it O(T²), then we should try and prove it [itex]\Omega(T^3)[/itex] or somesuch.



#8
May506, 12:13 AM

Sci Advisor
P: 1,253

!!!!!!
It can be done in O(T^2). I just figured it out. Use two backtoback stacks to represent the TM, like abczyx where  divides the two stacks and the left stack has a as its top level element, and the right stack has x as its top level element. Pushing onto a stack is easy: just write to the top of the stack. Removing an element from a stack is equally easy: just black it out. So the right stack might contain zy9x99w where the 9's are blacked out, and what that means is it contains wxyz with w on top, ignoring the 9's. The location of the tape head is represented by the space between the two stacks (as if you flipped the stacks around so they were facing one another). For example, to move the virtual tape head left, pop from the left stack and push to the right stack. 


#9
May506, 07:32 AM

Emeritus
Sci Advisor
PF Gold
P: 16,092

That's neat!
But as stated it requires a doublyinfinite tape. Well, maybe not. If you know how many steps you want to simulate, you can start sufficiently far out on your singlyinfinite tape so that you won't run off the left edge. And then to simulate an arbitrary number of steps, maybe you can use my trick! You could start X places out, and then run the simulation until you hit the left edge of your tape, and then copy the tape so that the center is at the X²nd cell and run until you hit the old stack, then copy so that the center is at the X^4 cell, and run... At least I hope you can pull that off. 


#10
May506, 08:00 AM

Sci Advisor
P: 1,253

To simulate it with a 1sided tape you can just interleave the stacks, so every other element starting from position 0 belongs to the left stack, and every other element starting from position 1 belongs to the right stack. So the twin stacks a99b9czy99xwvu would be represented as



Register to reply 
Related Discussions  
Turing machine help!  Engineering, Comp Sci, & Technology Homework  0  
Complement of Universal Turing Machine  Does this exist?  Set Theory, Logic, Probability, Statistics  4  
Turing machine problem  Engineering, Comp Sci, & Technology Homework  1  
Turing machine applied to virtual reality  General Discussion  7  
Turing machines  Calculus  5 