AoC 2017 Day 25: Turing

Source: The Halting Problem

Part 1: Implement a Turing machine defined as such:

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.


What is the final number of 1s on the tape?


AoC 2017 Day 18: Duetvm

Source: Duet

Part 1: Create a virtual machine with the following instruction set:

  • snd X plays a sound with a frequency equal to the value of X
  • set X Y sets register X to Y
  • add X Y set register X to X + Y
  • mul X Y sets register X to X * Y
  • mod X Y sets register X to X mod Y
  • rcv X recovers the frequency of the last sound played, if X is not zero
  • jgz X Y jumps with an offset of the value of Y, iff X is greater than zero

In most cases, X and Y can be either an integer value or a register.

What is the value recovered by rcv the first time X is non-zero?


AoC 2016 Day 23: Assembunny2

Source: Safe Cracking

Part 1: Take the assembunny interpreter from day 12 and add an instruction (tgl X) that modifies the code at an offset of X instructions.

  • inc becomes dec; any other one argument instruction (including tgl) becomes inc
  • jnz becomes cpy; any other two argument instructions become jnz
  • Toggling an instruction outside of the program does nothing (it does not halt execution)
  • If toggling produces an invalid instruction, ignore it

Run the given program with the initial register of a = 7. What is the final value in register a?


AoC 2016 Day 21: Scrambler

Source: Scrambled Letters and Hash

Part 1: Another virtual machine, of sorts. Start with the string abcdefgh and apply a sequence of the following commands to it:

  • swap position X with position Y = swap two positions
  • swap letter X with letter Y = swap to letters, no matter where they are
  • rotate (left|right) X steps = rotate forward or backward
  • rotate based on position of letter X = find X, rotate right based on its position; if the original position was >= 4, rotate one more1
  • reverse positions X through Y = reverse a subset of the string
  • move position X to position Y = take a character at a position out of the string and put it somewhere else specific


AoC 2016 Day 12: Assembunny

Source: Leonardo’s Monorail

Part 1: Create a virtual machine that has four registers (a, b, c, and d) and can process the following instructions:

  • cpy x y - copies x into y (x can be an integer or a register)
  • inc x - increases register x by one
  • dec x - decreases register x by one
  • jnz x y - jumps over y instructions if x is not zero (x can be an integer or a register)

What is the final value in register a?


'Tiny' Turing completeness without MMOV

Something was bugging me about my proof from yesterday. If we take another tack on proving Turing completeness, all we would have to prove is that we can simulate `SUBLEQ`. Since SUBLEQ is Turing complete, that’s all we need–just convert each SUBLEQ into a SUB, JZ, and a JLS. So that means that Tiny as written should be Turing complete.

So how does that work?


A 'Tiny' virtual machine in Racket

Today’s challenge at /r/dailyprogrammer asks to implement an assembler for a small virtual machine. It has only 16 mnemonics which in unique opcodes (each instruction can have multiple forms for if they’re accessing memory or literals), so it’s a simple virtual machine indeed. As a challenge, you’re supposed to write an interesting program (I actually wrote a virtual machine as well to test them). As an even better challenge, we’re supposed to prove that Tiny is Turing complete. Well, let’s get to it!