The Halting Problem

Advent of Code 2017 Day 25

Part 1

1. Recognizing the task
2. Understanding the language of the puzzle
3. Analyzing the example input
4. Forming a hypothesis based on the example running
5. Skip intro
6. Writing an algorithm that works on the example input
7. Refactoring my algorithm to work on my puzzle input

Recognizing the task

Abstractly, my task is:

Recreate the Turing machine and save the computer!

Algorithmically, my task is:

Solve for X such that X equals...

The diagnostic checksum a.k.a. the number of times 1 appears on the tape once the specified number of steps have been executed

Understanding the language of the puzzle

• To solve the puzzle, I must create a whole new Turing machine from scratch
• My input is a Turing machine blueprint
• A Turing machine has three parts: tape, cursor and states

The tape is simply depicted as:

... 0  0  0  0  0  0 ...

• It is an infinite list
• Each slot on the tape has two possible values: 0 (the starting value for all slots) and 1

The cursor is an exact location in the tape, represented by square brackets in the instructions:

... 0  0  0 [0] 0  0 ...

The states are sets of rules, each containing three instructions.

Based on whether the cursor is pointing at a 0 or a 1, the current state says:

1. What value to write at the current position of the cursor
2. Whether to move the cursor left or right one slot
3. And which state to use next

My impressions thus far

• An infinite list? That could be troublesome.
• Only modifying values, not deleting or creating? That could nullify performance concerns.
• Several states with conditions and instructions? Sounds like a list of functions...similar to the Intcode Computer I made throughout 2019.

Analyzing the example input

The following blueprint is offered as example:

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.

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

It specifies:

• Which state to use first
• The number of iterations to perform before counting all the 1s
• The quantity, names and rules for each state

As expected, each state consists of:

• Two conditions, based on the current value of the number at the location of the cursor in the tape
• For each condition, three instructions related to: 1) updating the value, 2) moving the cursor, 3) selecting the state to reference in the next iteration

Forming a hypothesis based on the example running

The instructions depict a running of the example blueprint:

... 0  0  0 [0] 0  0 ...
... 0  0  0  1 [0] 0 ...
... 0  0  0 [1] 1  0 ...
... 0  0 [0] 0  1  0 ...
... 0 [0] 1  0  1  0 ...
... 0  1 [1] 0  1  0 ...
... 0  1  1 [0] 1  0 ...

My observations:

• The input specified 6 steps
• The illustration depicts the same amount of slots
• Due to the cursor moving left and right, it only ever moves to four of the six slots (2/3)

Conclusion:

A predefined array filled with 0s likely does not need a length equal to the number of specified steps

• I hope this is true, because my puzzle input specifies several million steps
• I therefore intend to create an array that is of a size half the specified steps...at least to start
• I'll rely on errors to determine whether I must increase the size of the array

Skip intro

I'm not going to attempt to programmatically parse the puzzle input

• I'm less interested in converting text into rules
• I'm more interested in writing the states as functions and modifying an array

Writing an algorithm that works on the example input

Create an array with a length equal to the number of steps to perform, where each value is 0
Set cursor to the location that is either in the middle or the location to the right of what would be the middle element
Set state to the first function - stored as 0 to reference the first element in the array of states
Create a list of states, filled with functions that follow this structure:
  Store the value of the item in tape at the cursor
  If the value is 0
    Update the value to 0 or 1
    Decrement or increment the value stored in cursor
    Update state to the appropriate location in states
For i from 0 to the number of steps
  Invoke the function stored at the location in states equal to the current value of state
Return the number of 1s remaining in tape

My algorithm generates 3, as desired.

Refactoring my algorithm to work on my puzzle input

Now for the moment of truth:

• Will it finish in a reasonable amount of time for the amount of steps specified by my puzzle input?

Time to refactor!

...

• Refactored!
• Run!
• Finished in a second!
• Correct answer!

My algorithm only took a second to finish, even when the tape's length was equal to the amount of steps to process!

And when I adjust the array length to fractions of the fullest possible size, the algorithm only marginally gains performance...but it still works!

Part 2

Since this is Day 25, Part 2 only unlocks when I collect 49 stars. Which I never anticipate achieving. That's ok, though.

I did it!!

• I solved Part 1!
• I have solved 4/5 Day 25 Part 1s!