0
$\begingroup$

There is a long row of cells. Each cell contains 0 or 1. A machine is positioned immediately to the right of a series of uninterrupted 1’s followed by an uninterrupted series of 0’s. In the following graphic the machine is denoted by a yellow line. It is immediately to the right of a series of three 1’s followed by many 0’s.

start state

The machine is tasked to make a copy of the 1’s. When finished, the copy must be separated from the original by a single cell containing a 0. The final resting place for the machine is immediately to the right of the original 1’s. The following graphic shows the cells after the machine has fulfilled its copy task.

final state

At each step the machine must decide whether to move left one cell or right one cell, and whether to write 0 or 1 to the cell that it is currently positioned at. The machine cannot see what is in the neighboring cells. It can only see the value in the current cell. The machine makes its decision based purely in the current cell’s value and on the decisions it made previously.

I was able to program the machine to perform the copy operation using nine states (S0 – S8).

QUESTION: Is there a way for the machine to perform the copy operation in less than nine states?

The above graphics show just one example, in which three 1’s are copied. Of course, the machine must be able to perform the copy operation on any number of 1’s.

The diagram below shows the nine states that I needed. But first, here is an explanation of a notation used in the diagram:

notation used

Here is the strategy I used: As described above, the 1’s must be copied. How to know which 1’s have been copied and which remain to be copied? Answer: Shift the leftmost 1 to the left one cell and then copy it. Repeat for the next leftmost 1. And so on. There will be a series of shifted 1’s that have been copied and a series of unshifted 1’s that remain to be shifted and copied. Once there are no more unshifted 1’s, the machine is done. State 0 is the final state. State 1 is the starting state.

state transition diagram

Improve this question
$\endgroup$
  • 1
    $\begingroup$ Would 0011101110, 1110111000 and/or 00000011101110 have also been correct final tapes? Why or why not? Is the input a string 0^a 1^b 0^c with a + c > b and any valid final tape configuration 0^x 1^b 0 1^b 0^y where x + y + 2b + 1 = a + b + c? $\endgroup$ – Patrick87 Dec 25 '19 at 23:43
  • $\begingroup$ Hi @Patrick87. Yes, 0011101110, 1110111000 and 00000011101110 would also be correct final tapes since they have the original 1's copied and the copied 1's are separated from the original 1's by a single 0 cell.The (fascinating!) equations you list seem correct, I think. How do they help? $\endgroup$ – Roger Costello Dec 26 '19 at 0:09
  • $\begingroup$ I think the equations only help inasmuch as they make me confident I've understoof the problem correctly. $\endgroup$ – Patrick87 Dec 26 '19 at 0:44
  • $\begingroup$ The first two images are unnecessary; please don’t post images of text $\endgroup$ – D. Ben Knoble Dec 28 '19 at 14:48
0
$\begingroup$

Input: 0^a 1^b 0^c with a + c >= b + 1

Output: 0^z 1^b 0 1^b with b + z + 1 = a + c

Strategy:

  1. Move 1^b to the back of the tape
  2. Copy 1^b immediately to the left
  3. Clean up

States:

  • q0: scan left until you see 1; if beginning of tape, continue with state q3. Otherwise, change 1 to 0 and continue to q1
  • q1: scan right until blank or 1; then, move left and continue with state q2
  • q2: change 0 to 1, go left, and continue with q0
  • q3: scan right until you find 1; if you do, change 1 to 2, move left and continue with step q4; otherwise continue with state q6
  • q4: scan left until you find 0; then, move right and continue with state q5
  • q5: scan left until you find 0; when you do, change it to 2, move right, and continue with state q3
  • q6: scan left until you find a blank, changing all 2s to 1s along the way. then, halt-accept.

If you count halt-accept as its own state, this has 8 states, so it's at least one better than the one you gave (if this one works). Here's how I'd see it processing your example:

   0000001110: q0
-> 0000001101: q0, q1, q2, q0
-> 0000001011: q0, q1, q2, q0
-> 0000000111: q0, q1, q2, q0
-> 0000020211: q0, q3, q4, q5, q3
-> 0000220221: q3, q4, q5, q3
-> 0002220222: q3, q4, q5, q3
-> 0001110111: q3, q6, halt-accept
Improve this answer
$\endgroup$
  • $\begingroup$ Hi @Patrick87. I have only quickly reviewed your solution. I will study it in-depth tonight. One thing that caught my attention is "2" in a cell. The only allowable values in a cell are 0 and 1. $\endgroup$ – Roger Costello Dec 26 '19 at 12:06
  • $\begingroup$ @RogerCostello Are you sure? TMs generally are allowed to have different tape and input alphabets. If this question imposes this additional constraint on TMs then I agree this solution is probably not useful as it cannot easily be fixed. $\endgroup$ – Patrick87 Dec 26 '19 at 17:07
  • $\begingroup$ Hi @Patrick87. I imposed that restriction (cells may only have a value of 0 or 1) on myself. It is my understanding that if a larger vocabulary is permitted (e.g., cells may have the values 0,1, 2), then less states can be used to solve a problem. $\endgroup$ – Roger Costello Dec 26 '19 at 18:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.