A turing machine runner implemented with string substitution

turing.py

def generate_tape(tape, state, offset=1):
    head, *tail = tape
    *_, last = tape
    return (
        f"... {head}   " +
        f"   {head}   " * (offset - 1) +
        f"  [{head}|{state}]" +
        "".join(f"   {symbol}   " for symbol in tail) +
        f"   {last}   " * (offset - 1) +
        f"   {last} ...")


def generate_substitutions(rules, symbols):
    for (state, value), (new_state, new_value, move) in rules.items():
        # Formatting aliases
        a, b = state, new_state
        x, y = value, new_value

        if move == ">":
            for s in symbols:
                yield (
                    f"  [{x}|{a}]   {s}   ",
                    f"   {y}     [{s}|{b}]")
                yield (
                    f"  [{x}|{a}]   {s} ..",
                    f"   {y}     [{s}|{b}]   {s} ..")

        elif move == "<":
            for s in symbols:
                yield (
                    f"   {s}     [{x}|{a}]",
                    f"  [{s}|{b}]   {y}   ")
                yield (
                    f".. {s}     [{x}|{a}]",
                    f".. {s}     [{s}|{b}]   {y}   ")


def turing(rules, symbols=None, state=None, tape=None, offset=1):
    # Initialize
    if state is None:
        ((state, _), *_) = rules
    if symbols is None:
        symbols = list({symbol: _ for _, symbol in rules})
    if tape is None:
        tape = [symbols[0]]

    # Generate substitutions and tape
    substitutions = list(generate_substitutions(rules, symbols))
    tape = generate_tape(tape, state, offset)

    # Yield inital tape
    yield tape

    # Iterate over valid substitutions
    try:
        while True:
            tape = next(
                tape.replace(source, destination)
                for source, destination in substitutions
                if source in tape)
            yield tape
    # Until none is found
    except StopIteration:
        return


def main(tick=0.1):
    import time
    import shutil
    from colorama import Fore, Style

    _0 = Fore.BLUE + "0" + Fore.WHITE
    _1 = Fore.GREEN + "1" + Fore.WHITE
    a = Fore.RED + "a" + Fore.WHITE
    b = Fore.MAGENTA + "b" + Fore.WHITE
    c = Fore.CYAN + "c" + Fore.WHITE
    d = Fore.YELLOW + "d" + Fore.WHITE
    h = Fore.WHITE + "h" + Fore.WHITE

    beaver2 = {
        (a, _0): (b, _1, ">"),
        (a, _1): (b, _1, "<"),
        (b, _0): (a, _1, "<"),
        (b, _1): (h, _1, ">"),
    }

    beaver3 = {
        (a, _0): (b, _1, ">"),
        (a, _1): (h, _1, ">"),
        (b, _0): (c, _0, ">"),
        (b, _1): (b, _1, ">"),
        (c, _0): (c, _1, "<"),
        (c, _1): (a, _1, "<"),
    }

    beaver4 = {
        (a, _0): (b, _1, ">"),
        (a, _1): (b, _1, "<"),
        (b, _0): (a, _1, "<"),
        (b, _1): (c, _0, "<"),
        (c, _0): (h, _1, ">"),
        (c, _1): (d, _1, "<"),
        (d, _0): (d, _1, ">"),
        (d, _1): (a, _0, ">"),
    }

    columns = shutil.get_terminal_size((80, 20)).columns
    offset = (columns // 7 - 2) // 2

    for i, tape in enumerate(turing(beaver4, offset=offset)):
        time.sleep(tick)
        print(f"{Style.BRIGHT}{i:<3}: {tape}{Style.RESET_ALL}")


if __name__ == "__main__":
    main()