Skip to main content
deleted 2 characters in body
Source Link
Vor
  • 12.7k
  • 1
  • 30
  • 62

It is obvious that you can't handle all the right moves at the same time, so the trick is to use a special symbol to mark the head position ($\#$) and place it on the left of the symbol under the head:

queue: 0100100#1  equivalent to tape: __0100100[1]___

Now you pop the symbols from the right and re-push them on the left but with one symbol of delay (you buffer one symbol using the internal states). When you read a symbol $x$ and the internal buffer contains $z$ then you re-push $z$ on the queue:

queue: 0100101#1  pop:   buf:* (initially the buffer contains the * marker, see below)     
queue:  0100101#  pop:1  buf:* 
queue:  &0100101*0100101  pop:#  buf:1  

When you pop $\#$ then you know that the symbol $x$ in the (internal) buffer is the symbol under the head, and you can apply the corresponding transition:

** if the transition says to write symbol $y$ and goto to $Right$ then you push $\#$ and the $y$ on the left of the queue.

 queue:    *0100101   pop:#  buf:1  apply transition Write 0 go Right
 queue:  0#*0100101   pop:   buf:  
 queue:   0#*010010   pop:1  buf:
 queue:    0#*01001   pop:0  buf:1
 queue:    10#*0100   pop:1  buf:0
 ...

Then you continue the pop-push operations until you find again the $\#$.

** if the transition says to write symbol $y$ and goto to $Left$ then you can simply push $y$ on the left of the queue and keep the $\#$ in the internal buffer, read the next symbol and apply another transition until you find a Right move again:

queue:    *0100101   pop:#  buf:1  apply transition Write 0 go Left
queue:    0*010010   pop:1  buf:#  apply transition Write 1 go Left
queue:    10*01001   pop:0  buf:#  apply transition Write 1 go Right
queue:  1#10*01001   pop:   buf:  
...

The special symbol $*$ marks the begin/end of the tape and you can use it to handle the tape expansion on both directions. Now, you should be able to discover how by yourself. And if you want to be rigorous, you should also consider tehthe special initial case (inin which the queue doesn't contain the head symbol #).

It is obvious that you can't handle all the right moves at the same time, so the trick is to use a special symbol to mark the head position ($\#$) and place it on the left of the symbol under the head:

queue: 0100100#1  equivalent to tape: __0100100[1]___

Now you pop the symbols from the right and re-push them on the left but with one symbol of delay (you buffer one symbol using the internal states). When you read a symbol $x$ and the internal buffer contains $z$ then you re-push $z$ on the queue:

queue: 0100101#1  pop:   buf:* (initially the buffer contains the * marker, see below)     
queue:  0100101#  pop:1  buf:* 
queue:  &0100101  pop:#  buf:1  

When you pop $\#$ then you know that the symbol $x$ in the (internal) buffer is the symbol under the head, and you can apply the corresponding transition:

** if the transition says to write symbol $y$ and goto to $Right$ then you push $\#$ and the $y$ on the left of the queue.

 queue:    *0100101   pop:#  buf:1  apply transition Write 0 go Right
 queue:  0#*0100101   pop:   buf:  
 queue:   0#*010010   pop:1  buf:
 queue:    0#*01001   pop:0  buf:1
 queue:    10#*0100   pop:1  buf:0
 ...

Then you continue the pop-push operations until you find again the $\#$.

** if the transition says to write symbol $y$ and goto to $Left$ then you can simply push $y$ on the left of the queue and keep the $\#$ in the internal buffer, read the next symbol and apply another transition until you find a Right move again:

queue:    *0100101   pop:#  buf:1  apply transition Write 0 go Left
queue:    0*010010   pop:1  buf:#  apply transition Write 1 go Left
queue:    10*01001   pop:0  buf:#  apply transition Write 1 go Right
queue:  1#10*01001   pop:   buf:  
...

The special symbol $*$ marks the begin/end of the tape and you can use it to handle the tape expansion on both directions. Now, you should be able to discover how by yourself. And if you want to be rigorous, you should also consider teh special initial case (in which the queue doesn't contain the head symbol #).

It is obvious that you can't handle all the right moves at the same time, so the trick is to use a special symbol to mark the head position ($\#$) and place it on the left of the symbol under the head:

queue: 0100100#1  equivalent to tape: __0100100[1]___

Now you pop the symbols from the right and re-push them on the left but with one symbol of delay (you buffer one symbol using the internal states). When you read a symbol $x$ and the internal buffer contains $z$ then you re-push $z$ on the queue:

queue: 0100101#1  pop:   buf:* (initially the buffer contains the * marker, see below)     
queue:  0100101#  pop:1  buf:* 
queue:  *0100101  pop:#  buf:1  

When you pop $\#$ then you know that the symbol $x$ in the (internal) buffer is the symbol under the head, and you can apply the corresponding transition:

** if the transition says to write symbol $y$ and goto to $Right$ then you push $\#$ and the $y$ on the left of the queue.

 queue:    *0100101   pop:#  buf:1  apply transition Write 0 go Right
 queue:  0#*0100101   pop:   buf:  
 queue:   0#*010010   pop:1  buf:
 queue:    0#*01001   pop:0  buf:1
 queue:    10#*0100   pop:1  buf:0
 ...

Then you continue the pop-push operations until you find again the $\#$.

** if the transition says to write symbol $y$ and goto to $Left$ then you can simply push $y$ on the left of the queue and keep the $\#$ in the internal buffer, read the next symbol and apply another transition until you find a Right move again:

queue:    *0100101   pop:#  buf:1  apply transition Write 0 go Left
queue:    0*010010   pop:1  buf:#  apply transition Write 1 go Left
queue:    10*01001   pop:0  buf:#  apply transition Write 1 go Right
queue:  1#10*01001   pop:   buf:  
...

The special symbol $*$ marks the begin/end of the tape and you can use it to handle the tape expansion on both directions. Now, you should be able to discover how by yourself. And if you want to be rigorous, you should also consider the special initial case in which the queue doesn't contain the head symbol #.

Source Link
Vor
  • 12.7k
  • 1
  • 30
  • 62

It is obvious that you can't handle all the right moves at the same time, so the trick is to use a special symbol to mark the head position ($\#$) and place it on the left of the symbol under the head:

queue: 0100100#1  equivalent to tape: __0100100[1]___

Now you pop the symbols from the right and re-push them on the left but with one symbol of delay (you buffer one symbol using the internal states). When you read a symbol $x$ and the internal buffer contains $z$ then you re-push $z$ on the queue:

queue: 0100101#1  pop:   buf:* (initially the buffer contains the * marker, see below)     
queue:  0100101#  pop:1  buf:* 
queue:  &0100101  pop:#  buf:1  

When you pop $\#$ then you know that the symbol $x$ in the (internal) buffer is the symbol under the head, and you can apply the corresponding transition:

** if the transition says to write symbol $y$ and goto to $Right$ then you push $\#$ and the $y$ on the left of the queue.

 queue:    *0100101   pop:#  buf:1  apply transition Write 0 go Right
 queue:  0#*0100101   pop:   buf:  
 queue:   0#*010010   pop:1  buf:
 queue:    0#*01001   pop:0  buf:1
 queue:    10#*0100   pop:1  buf:0
 ...

Then you continue the pop-push operations until you find again the $\#$.

** if the transition says to write symbol $y$ and goto to $Left$ then you can simply push $y$ on the left of the queue and keep the $\#$ in the internal buffer, read the next symbol and apply another transition until you find a Right move again:

queue:    *0100101   pop:#  buf:1  apply transition Write 0 go Left
queue:    0*010010   pop:1  buf:#  apply transition Write 1 go Left
queue:    10*01001   pop:0  buf:#  apply transition Write 1 go Right
queue:  1#10*01001   pop:   buf:  
...

The special symbol $*$ marks the begin/end of the tape and you can use it to handle the tape expansion on both directions. Now, you should be able to discover how by yourself. And if you want to be rigorous, you should also consider teh special initial case (in which the queue doesn't contain the head symbol #).