Source: The Halting Problem

Part 1: Implement a Turing machine defined as such:

Begin in state A. Perform a diagnostic checksum after 6 steps.

In state A: If the current value is 0: - Write the value 1. - Move one slot to the right. - Continue with state B. If the current value is 1: - Write the value 0. - Move one slot to the left. - Continue with state B.

…

As we did in part 1 of day 22, we’ll use a set to store the current state (store 1, if an index is not in the set, it’s 0). That gives us the ability to grow unbounded (so long as we have enough RAM).

Once you have that, actually running the Turing machine is pretty straight forward:

for tick in range(breakpoint):
    value = 1 if pointer in one_bits else 0

    if value and not transitions[state, value, 'value']:
        one_bits.remove(pointer)
    elif not value and transitions[state, value, 'value']:
        one_bits.add(pointer)

    pointer += transitions[state, value, 'offset']
    state = transitions[state, value, 'state']

print(len(one_bits))

It’s not the fastest thing in the world, but it works well enough:

$ python3 run-all.py day-25

day-25  python3 turing.py input.txt     79.73910212516785       2870

Since it’s the last day, there’s only one part. A fun year. Check out the index post for a list of this year’s posts.

Merry Christmas! ☃️