0
$\begingroup$

Assuming a single tape (which extends infinitely in both directions) Turing Machine,

If its head and tape contents start at position $0$ and the tape contents are only extended to the right, then it would suffice to enumerate all odd binary numbers (or if there are more than two symbols, those not starting or ending with any number of blank symbols) to ensure that no tape configuration is generated twice (000...1...000 and 000...10...000 being duplicates otherwise). So in the two-symbol case where 0 is also the blank symbol: 0 (for the completely empty tape), 1, 11, 101, 111 etc.

But this stops working when considering that the head may start anywhere relative to the program, where the head position may be any integer.

So given a fixed program, a machine initialized to

0001000
  ^
  head

will behave differently to

0001000
   ^
   head

But of course there are infinitely many starting positions for the head to the left and right with a single 1 on the tape. Enumerating these would have the consequence of never getting to enumerate all the other possible tape contents. I assume there exists some diagonalization trick that would ensure all (tape, head position) configurations to still be reached?

$\endgroup$

1 Answer 1

0
$\begingroup$

It seems to suffice to enumerate all binary strings, mirror/flip each around the least significant digit also (to ensure that all strings prefixed by any number of 0's are generated) and, if the tape content doesn't end in blank symbol(s), shift them over to all positions except the last (to prevent duplicates with the mirror operation).

000... ...000<- blank symbols
      ^-head position
      0
      1
     10
      01 #mirror flip around head position
     11
      11
    100
      001
    101
      101
     101 # shifting to the right
    110
      011
    111
      111
     111 # shifting to the right
   1000
      0001
   1001
      1001
    1001 # shifting right twice, here...
     1001 # ...and here
def config_generator():
    i = 0
    while True:
        b = bin(i)[2:]
        yield b, 0
        # Don't generate 0 or 1 twice (mirrored)
        if i < 2:
            i += 1
            continue

        # In the 2 symbol (0 or 1) case, the tape not ending with a blank symbol can be ensured by checking if the number is odd (ending with a binary 1)
        if i % 2 == 1:
            for l in range(len(b)-2):
                yield b, -l-1
        
        yield b[::-1], -len(b)
        
        i += 1

gen = config_generator()

for i in range(64):
    tape, head = next(gen)
    print(tape)
    print(" "*(len(tape)+head-1)+"^")
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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