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.
…
Part 1: Create a virtual machine with the following instruction set:
snd Xplays a sound with a frequency equal to the value ofXset X Ysets registerXtoYadd X Yset registerXtoX + Ymul X Ysets registerXtoX * Ymod X Ysets registerXtoX mod Yrcv Xrecovers the frequency of the last sound played, ifXis not zerojgz X Yjumps with an offset of the value ofY, iffXis greater than zero
In most cases,
XandYcan be either an integer value or a register.
What is the value recovered by
rcvthe first timeXis non-zero?
Part 1: Running on the string
a...papply a series of the following commands:
sXrotates the string right byXpositionsxX/Yswaps positionsXandYpA/Bswaps the lettersAandBno matter their positions
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?
Part 1: Take the assembunny interpreter from day 12 and add one new instruction (out
x) which transmits the valuex(either an integer or register). Find the lowest value we can initializeato so that theoutput signals form an infinite repeating pattern of0,1,0,1, …
Part 1: Take the assembunny interpreter from day 12 and add an instruction (tgl
X) that modifies the code at an offset ofXinstructions.
incbecomesdec; any other one argument instruction (includingtgl) becomesincjnzbecomescpy; any other two argument instructions becomejnz- 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 registera?
Part 1: Create a virtual machine that has four registers (
a,b,c, andd) and can process the following instructions:
cpy x y- copiesxintoy(xcan be an integer or a register)inc x- increases registerxby onedec x- decreases registerxby onejnz x y- jumps overyinstructions ifxis not zero (xcan be an integer or a register)
What is the final value in register
a?
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?
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!