# '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!