The Halting Problem

In [75]:

    

import re

def parse_blueprint(input_path):
    blueprint = {}
    p = re.compile('Begin in state (?P<initial_state>.*).\nPerform a diagnostic checksum after (?P<steps>.*) steps.')
    q = re.compile('In state (?P<state>.*):\n  If the current value is 0:\n    - Write the value (?P<write_value_0>.*).\n    - Move one slot to the (?P<move_0>.*).\n    - Continue with state (?P<new_state_0>.*).\n  If the current value is 1:\n    - Write the value (?P<write_value_1>.*).\n    - Move one slot to the (?P<move_1>.*).\n    - Continue with state (?P<new_state_1>.*).')
    with open(input_path, 'rt') as f_input:
        data = f_input.read()
    lines = data.split('\n\n')
    m = p.search(lines[0])
    initial_state = m.group("initial_state")
    steps = int(m.group("steps"))
    for paragraph in lines[1:]:
        m = q.search(paragraph)
        blueprint[m.group("state")] = {0: {'write': int(m.group("write_value_0")), 'move': m.group("move_0"), 'continue': m.group("new_state_0")},
                                       1: {'write': int(m.group("write_value_1")), 'move': m.group("move_1"), 'continue': m.group("new_state_1")}}
    return initial_state, steps, blueprint


    

In [146]:

    

class TuringMachine(object):
    
    def __init__(self, initial_state, blueprint):
        self.state = initial_state
        self.blueprint = blueprint
        self.tape = [0]
        self.head = 0
        
    def update(self):
        action = self.blueprint[self.state][self.tape[self.head]]
        write, move = action['write'], action['move']
        self.tape[self.head] = write
        self.head += 1*(move == 'right') - 1*(move == 'left')
        if self.head >= len(self.tape): self.tape.append(0)    
        if self.head < 0: 
            self.tape = [0] + self.tape[:]
            self.head = 0
        self.state = action['continue']

def checksum(input_path):
    initial_state, steps, blueprint_test = parse_blueprint(input_path)
    tm = TuringMachine(initial_state, blueprint_test)
    for _ in range(steps):
        tm.update()
    return sum(tm.tape)


    

In [147]:

    

assert(checksum('input.test1.txt') == 3)


    

In [148]:

    

checksum('input.txt')


    

    
Out[148]:





4217