The Halting Problem — Python — #adventofcode Day 25

Date:
Series: Advent of Code 2017
Tags: [Technology] [Learning] [Advent of Code] [Python]

Series

This post is part of the series Advent of Code 2017

Today’s challenge, takes us back to a bit of computing history: a good old-fashioned Turing Machine.

→ Full code on GitHub

!!! commentary Today’s challenge was a nice bit of nostalgia, taking me back to my university days learning about the theory of computing. Turing Machines are a classic bit of computing theory, and are provably able to compute any value that is possible to compute: a value is computable if and only if a Turing Machine can be written that computes it (though in practice anything non-trivial is mind-bendingly hard to write as a TM).

A bit of a library-fest today, compared to other days!

from collections import deque, namedtuple
from collections.abc import Iterator
from tqdm import tqdm
import re
import fileinput as fi

These regular expressions are used to parse the input that defines the transition table for the machine.

RE_ISTATE = re.compile(r'Begin in state (?P<state>\w+)\.')
RE_RUNTIME = re.compile(
    r'Perform a diagnostic checksum after (?P<steps>\d+) steps.')
RE_STATETRANS = re.compile(
    r"In state (?P<state>\w+):\n"
    r"  If the current value is (?P<read0>\d+):\n"
    r"    - Write the value (?P<write0>\d+)\.\n"
    r"    - Move one slot to the (?P<move0>left|right).\n"
    r"    - Continue with state (?P<next0>\w+).\n"
    r"  If the current value is (?P<read1>\d+):\n"
    r"    - Write the value (?P<write1>\d+)\.\n"
    r"    - Move one slot to the (?P<move1>left|right).\n"
    r"    - Continue with state (?P<next1>\w+).")
MOVE = {'left': -1, 'right': 1}

A namedtuple to provide some sugar when using a transition rule.

Rule = namedtuple('Rule', 'write move next_state')

The TuringMachine class does all the work.

class TuringMachine:
    def __init__(self, program=None):
        self.tape = deque()
        self.transition_table = {}
        self.state = None
        self.runtime = 0
        self.steps = 0
        self.pos = 0
        self.offset = 0

        if program is not None:
            self.load(program)

    def __str__(self):
        return f"Current: {self.state}; steps: {self.steps} of {self.runtime}"

Some jiggery-pokery to allow us to use self[pos] to reference an infinite tape.

    def __getitem__(self, i):
        i += self.offset
        if i < 0 or i >= len(self.tape):
            return 0
        else:
            return self.tape[i]

    def __setitem__(self, i, x):
        i += self.offset
        if i >= 0 and i < len(self.tape):
            self.tape[i] = x
        elif i == -1:
            self.tape.appendleft(x)
            self.offset += 1
        elif i == len(self.tape):
            self.tape.append(x)
        else:
            raise IndexError('Tried to set position off end of tape')

Parse the program and set up the transtion table.

    def load(self, program):
        if isinstance(program, Iterator):
            program = ''.join(program)

        match = RE_ISTATE.search(program)
        self.state = match['state']

        match = RE_RUNTIME.search(program)
        self.runtime = int(match['steps'])

        for match in RE_STATETRANS.finditer(program):
            self.transition_table[match['state']] = {
                int(match['read0']): Rule(write=int(match['write0']),
                                          move=MOVE[match['move0']],
                                          next_state=match['next0']),
                int(match['read1']): Rule(write=int(match['write1']),
                                          move=MOVE[match['move1']],
                                          next_state=match['next1']),
            }

Run the program for the required number of steps (given by self.runtime). tqdm isn’t in the standard library but it should be: it shows a lovely text-mode progress bar as we go.

    def run(self):
        for _ in tqdm(range(self.runtime),
                      desc="Running", unit="steps", unit_scale=True):
            read = self[self.pos]
            rule = self.transition_table[self.state][read]
            self[self.pos] = rule.write
            self.pos += rule.move
            self.state = rule.next_state

Calculate the “diagnostic checksum” required for the answer.

    @property
    def checksum(self):
        return sum(self.tape)

Aaand GO!

machine = TuringMachine(fi.input())
machine.run()
print("Checksum:", machine.checksum)

Webmentions

You can respond to this post, "The Halting Problem — Python — #adventofcode Day 25", by: liking, boosting or replying to a tweet or toot that mentions it; or sending a webmention from your own site to https://erambler.co.uk/blog/day-25/

Comments & reactions haven't loaded yet. You might have JavaScript disabled but that's cool 😎.

Comments

Powered by Cactus Comments 🌵