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?





Most of this problem actually came down to reading the input:

```python
# Map of (current state, current value, key) -> value
# key is one of value, offset, state
transitions = {}
breakpoint = 0
state = None
pointer = 0
one_bits = set()

for line in lib.input():
    line = line.strip('- ')
    arg = line.split()[-1][:-1]

    if arg == 'steps':
        arg = line.split()[-2]

    try:
        arg = int(arg)
    except:
        pass

    # Store values based on that argument
    if line.startswith('Begin'):
        state = arg
    elif line.startswith('Perform'):
        breakpoint = arg
    elif line.startswith('In'):
        current_state = arg
    elif line.startswith('If'):
        current_value = arg
    elif line.startswith('Write'):
        transitions[current_state, current_value, 'value'] = arg == 1
    elif line.startswith('Move'):
        transitions[current_state, current_value, 'offset'] = 1 if arg == 'right' else -1
    elif line.startswith('Continue'):
        transitions[current_state, current_value, 'state'] = arg

As we did in part 1 of day 22, we’ll use a set to store the current state (store 1, if an index is not in the set, it’s 0). That gives us the ability to grow unbounded (so long as we have enough RAM).

read more...

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?

read more...

Source: Permutation Promenade

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

read more...

Source: I Heard You Like Registers¹

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?

read more...

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, …

read more...

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?

read more...

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 more¹
• 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

read more...

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?

read more...

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?

read more...

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!

read more...