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

# 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 2017 Day 16: Swing Your Partner

Part 1: Running on the string a...p apply a series of the following commands:

• sX rotates the string right by X positions
• xX/Y swaps positions X and Y
• pA/B swaps the letters A and B no matter their positions

# AoC 2017 Day 8: Conditiputer

### Source: I Heard You Like Registers1

Part 1: Given a set of registers initialized to 0, interpret a series of instruction of the form:

• {register} (inc|dec) {number|register} if {number|register} (<|<=|=|!=|=>|>) {number|register}

What is the largest value in any register?

# AoC 2016 Day 25: Assembunny3

### Source: Clock Signal

Part 1: Take the assembunny interpreter from day 12 and add one new instruction (out x) which transmits the value x (either an integer or register). Find the lowest value we can initialize a to so that the output signals form an infinite repeating pattern of 0, 1, 0, 1, …

# 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?