Module day25

The Halting Problem

The input is parsed into a 2 dimensional array covering each possible combination of state and tape value at the cursor. Each transition is then computed via a lookup into this array.

To speed things up by about ten times, multiple transitions are then precomputed to allow skipping forward multiple steps at a time.

For each of the 6 * 256 = 1536 combinations of a tape with 4 values to the left and 3 values to the right of the cursor, the turing machine is computed one steps at a time until the cursor leaves the area to the left or to the right. For example:

    State: A            => State: B
      1 0 1 0 [1] 0 0 1     [0] 0 1 0 0 1 1 0

    State: B
      t t t t [0] 0 1 0

In this example the tape then advances four bits to the left, loading the four values of t then the next batch lookup is performed.

Structs

Input

Rule 🔒

Skip 🔒

Functions

parse

Parse the input into 12 rules for each possible combination of state and value at the cursor.

part1

part2

turing 🔒