complete.py

# This script runs all possible turing machines on all possible (finite) inputs
# idea by Toby Ord: http://www.amirrorclear.net/academic/ideas/simulation/index.html

from itertools import product

tms = []

# https://stackoverflow.com/q/79023187/9779026
def binary_split(v):
	# works for v > 0
	x = 0
	y = 0
	while v > 0:
		if v&1 == 1:
			break
		v >>= 1
		x += 1
	y = (v - 1)>>1
	return x,y

def bin2list(v):
	return [int(x) for x in v]

# https://cs.stackexchange.com/a/168156/88220
def tape_generator():
    i = 0
    while True:
        b = bin(i)[2:]
        yield bin2list(b), len(b)-1
        # 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 bin2list(b), len(b)-l-1
        
        yield bin2list(b[::-1]), len(b)-len(b)-1
        
        i += 1

# this should be cached, but isn't, oh well
# the program will spend the majority of time in the Turing Machine step function anyway i guess
def i_th_tape(i):
	gen = tape_generator()
	for i in range(i-1):
		next(gen)
	return next(gen)

symbols = [0,1]
directions = [-1,1]

def table_generator():
	n_states = 1
	while True:
		choices = [symbols, directions, list(range(n_states+1))]
		for table in product(repeat=n_states*len(symbols), *choices):
			yield table
		n_states += 1

def i_th_table(i):
	gen = table_generator()
	for i in range(i-1):
		next(gen)
	return next(gen)

class TM:
	def __init__(self, i):
		table_number, tape_number = binary_split(i)
		self.table = i_th_table(table_number)
		self.tape, self.head = i_th_tape(tape_number)
		self.state = 0
		#print(self.table)
		#print(self.tape)

	def step(self):
		#print(self.head, self.tape, self.table, self.state)
		# if in the halting state, do nothing
		if self.state == len(self.table):
			return
			
		read = self.tape[self.head]
		
		table_index = self.state*2+read
		self.tape[self.head] = self.table[table_index]
		move = self.table[table_index+1]
		self.state = self.table[table_index+2]
		self.head += move
		if self.head == -1:
			self.tape = [0] + self.tape
			self.head = 0
		elif self.head == len(self.tape):
			self.tape.append(0)

i = 1
while True:
	print(i)
	tms.append(TM(i))

	for j in range(i):
		tms[j].step()

	i += 1