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!
It’s been rather a while since I’ve worked out a Programming Praxis problem, but they posted a new one yesterday, so now seems as good a time as any. The problem is relatively simple:
Given a linked list, swap the kth node from the head of the list with the kth node from the end of the list.
Since all lists in Scheme are linked lists, that part seems easy enough. To make the problem a little more interesting however, I’m going to work it out in a purely functional manner: no mutation.