Build enumerator (printer) for { 0 ^ (3 ^ n) | n >=0} with at most 10 states including print and halt, limited alphabet?

user_10035170 0
Viewed 462

I have a task to build an enumerator (a turing machine which also prints to the output tape and outputs it by going to the print state) for the language {0 ^ (3 ^ n) | n >= 0} where:

1) The number of states must be at most 10 (including print and halt states, they are part of the 10 states)

2) Gamma, the printer alphabet is {0, x, space} and nothing more.

3) The output tape alphabet is {0}.

I've tried numerous times to build it with at most 10 states but managed to use 11 and not 10. My idea was to erase each 0 with a space, then iterate past a certain delimiter say X, and write 3 0s for each deleted 0 before the delimiter. For example space|x|space,space,space|x|000000000|x|. "|" is just to emphasize the delimiter for this question, the spaces are the previous 0's overwritten - after overwriting each 0 with space i iterate past the X and append 3 0s at the end.

Each time i failed miserably lacking one more state. I've run out of ideas...help ?

Thanks

computation-theory computer-science turing-machines algorithm
1 Answers

There are lots of machines that can do this. Here's an example of one. It happens to have a smaller number of states than required.

The basic idea is this:

  1. start off by printing 0^(3^0) = 0^1 = 0 to the tape.
  2. immediately after doing so, enter print since 0 is a string we need to enumerate.
  3. after printing, convert all 0 on the tape to spaces, reading left to right
  4. after converting all 0 to spaces, convert the rightmost space to a 0, then add two 0 to the end of the tape
  5. continue step 4 until all spaces are erased
  6. the tape contents are a new string to enumerate, since we took a previous string of the form 0^(3^n) and tripled every occurrence of 0, giving the string 0^(3^(n+1)).

The states look something like this:

 Q     T    Q'    T'    Mv
--    --    --    --    --
q0     x    pr     0    same
print  0    q1    sp    same
q1     0    q1    sp    right
q1     x    q2     x    left
q2     x    pr     x    right
q2    sp    q3     0    right
q2     0    q2     0    left
q2     x    pr     x    right
q3     0    q3     0    right
q3     x    q4     0    right
q4     x    q2     0    left

And here's what it looks like up through printing 0^(3^2) = 0^9:

xxxxxxxxxxxxxxxxxxxx
 ^ q0
x0xxxxxxxxxxxxxxxxxx
 ^ pr
x xxxxxxxxxxxxxxxxxx
 ^ q1
x xxxxxxxxxxxxxxxxxx
  ^ q1
x xxxxxxxxxxxxxxxxxx
 ^ q2
x0xxxxxxxxxxxxxxxxxx
  ^ q3
x00xxxxxxxxxxxxxxxxx
   ^ q4
x000xxxxxxxxxxxxxxxx
   ^ q2
x000xxxxxxxxxxxxxxxx
  ^ q2
x000xxxxxxxxxxxxxxxx
 ^ q2
x000xxxxxxxxxxxxxxxx
^ q2
x000xxxxxxxxxxxxxxxx
 ^ pr
x 00xxxxxxxxxxxxxxxx
  ^ q1
x  0xxxxxxxxxxxxxxxx
   ^ q1
x   xxxxxxxxxxxxxxxx
    ^ q1
x   xxxxxxxxxxxxxxxx
   ^ q2
x  0xxxxxxxxxxxxxxxx
    ^ q3
x  00xxxxxxxxxxxxxxx
     ^ q4
x  000xxxxxxxxxxxxxx
    ^ q2
x  000xxxxxxxxxxxxxx
   ^ q2
x  000xxxxxxxxxxxxxx
  ^ q2
x 0000xxxxxxxxxxxxxx
   ^ q3
x 0000xxxxxxxxxxxxxx
    ^ q3
x 0000xxxxxxxxxxxxxx
     ^ q3
x 0000xxxxxxxxxxxxxx
      ^ q3
x 00000xxxxxxxxxxxxx
       ^ q4
x 000000xxxxxxxxxxxx
      ^ q2
...
x 000000xxxxxxxxxxxx
 ^ q2
x0000000xxxxxxxxxxxx
  ^ q3
...
x0000000xxxxxxxxxxxx
        ^ q3
x00000000xxxxxxxxxxx
         ^ q4
x000000000xxxxxxxxxx
        ^ q2
...
x000000000xxxxxxxxxx
^
x000000000xxxxxxxxxx
 ^ pr
...
user_8472690
Related