# Generating all unique (tape content, head position) possibilities for a Turing Machine

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
^


will behave differently to

0001000
^


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?

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
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):