## DEV Community # The Halting Problem

## Part 1

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

Recreate the Turing machine and save the computer!

#### 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 ...
``````

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 `1`s
• 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  1  0 ...
... 0  0  0  1  0 ...
... 0  0  0  1  0 ...
... 0  1  0  1  0 ...
... 0  1  0  1  0 ...
... 0  1  1  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!

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!