turing.py

gistfile1.txt

import math

def _pair(x, y):
    return (((x + y) * (x + y + 1)) >> 1) + y

def decode(s):
    states = []
    for state in s.split("_"):
        e0 = [int(state[0]), state[1].lower(), ord(state[2].lower()) - 97]
        if e0[2] == 25:
            e0[2] = s.count("_") + 1

        e1 = [int(state[3]), state[4].lower(), ord(state[5].lower()) - 97]
        if e1[2] == 25:
            e1[2] = s.count("_") + 1

        states.append([e0, e1])

    return states

def encode(states):
    x = 0
    for i in range(len(states) - 1, -1, -1):
        for n, d, s in states[i][::-1]:
            x *= len(states) + 1
            x += s
            x <<= 1
            x |= {"l": 0, "r": 1}[d]
            x <<= 1
            x |= n

    return _pair(x, len(states))

def f(_x):
    w = (math.isqrt(1 + 8 * _x) - 1) >> 1
    y = _x - ((w ** 2 + w) >> 1)
    x = w - y

    state = 0
    index = 0
    tape = []

    m = []

    for i in range(0, y):
        a = (x & 0b01, ((x & 0b10) >> 1) * 2 - 1, (x >> 2) % (y + 1))
        x >>= 2
        x //= (y + 1)
        b = (x & 0b01, ((x & 0b10) >> 1) * 2 - 1, (x >> 2) % (y + 1))
        x >>= 2
        x //= (y + 1)

        m.append((a, b))

    while True:
        if len(tape) <= index:
            tape.append(0)

        n, d, state = m[state][tape[index]]

        tape[index] = n
        index += d

        if state == y:
            return tape

        if index < 0:
            index = 0
            tape.insert(0, 0)

5 state busy beaver:
1RB1LC_1RC1RB_1RD0LE_1LA1LD_1RZ0LA
[[[1, 'r', 1], [1, 'l', 2]], [[1, 'r', 2], [1, 'r', 1]], [[1, 'r', 3], [0, 'l', 4]], [[1, 'l', 0], [1, 'l', 3]], [[1, 'r', 5], [0, 'l', 0]]]
3358402454383924230578783