Yo dawg I heard you like esoteric programming languages...

... so I made a compiler to turn a Turing tarpit into a one instruction set computer so you can use the processor inside your processor to compute between cycles of computation.

There's this wonderful paper detailing the computation model discovered in the x86 memory management unit, or MMU for short. Basically, by setting up the page table right, you can arrange for a page fault handler to lead to another page fault. If you set things up juuuust right, you can get a whole cascade of page faults. You can then modulate this to implement a single instruction, Harvard-architecture, Turing-complete computer using Move-Decrement-BranchIfZero, or MOVDBZ for short, with the following semantics in pseudocode:

MOVDBZ (x ← y-1) THEN l ELSE l′ = do
  val ← read x
  if val == 0 then do
    write y 0
    jump l
  else do
    write y (val-1)
    jump l′

I'm going to refer to x and y as the source and target registers below, but it's important to understand that these are not the real registers of the x86 processor that we are talking about here; rather, these are the registers of this virtual machine living inside the MMU. The term Harvard architecture means the instruction labels l and l′ come from a completely separate namespace as the register (c.f. von Neumann computer).

Another important thing is that from the real x86 processor's point of view, the whole computation takes up zero cycles. That is because the resolution of the page fault happens between (or, to be more precise, in the middle of) instructions, so the whole cascade will be executed by the MMU before the next x86 instruction runs.

The paper linked above has all the details; this is just a summary to motivate what follows. Readers of my blog already know Brainfuck is Turing-complete, since we managed to compile register machine code into Brainfuck. So let's continue that chain of reasoning (motivated by this Proggit comment), and prove the Turing-completeness of MovDBz by compiling Brainfuck into MovDBz.

First of all, I'm going to add two new instructions to our one-instruction machine; hopefully we can all agree they don't change the spirit of the challange:

• HALT is already implicitly part of the original language, since you can set up parts of the page table in such a way that the cascade stops
• I've added PRINT to be able to do some I/O. We won't be aiming for input, so the Brainfuck instruction , is not going to be supported.

Here's a straightforward interpreter for this dialect of MovDBz.

At initial glance, there seem to be two tricky aspects of Brainfuck with respect to MovDBz:

• Brainfuck has (limited) indirect addressing: there's a pointer register that addresses into the other data cells. MovDBz has nothing like that: every instruction has the source and target registers hardcoded.
• Brainfuck has increment and decrement operators, whereas MovDBz only has decrement.

Indirect addressing

The first problem is solved by basically turning this:

into this:

This latter construct is easy to implement if we nominate one of our MovDBz registers as a temporary register tmp:

where n is the maximum index of Brainfuck cells.

Note that this means the generated MovDBz program's size will be linear in the number of Brainfuck cells. The Brainfuck spec calls for 30,000 cells; when compiling to MovDBz, it is usually a good idea to use a lot less cells.

Incrementing

At first glance, it might seem impossible to implement incrementing when all we have is a single decrement operator. Modular arithmetic comes to the rescue: since x + 1 ≡ x - 255 (mod 256), we can do repeated decrements (255 times) to emulate incrementing. Of course, we also have to handle specially the case when the value gets to 0.

So with the help of a constant register C256 we keep clamped to 256, we can turn this:

Into this:

We can implement incrementing the pointer (> in Brainfuck) similarily, by having another constant register storing the number of cells (i.e. n+1).

Putting it all together

To prototype these ideas, I've written a compiler that uses the above techniques to turn Brainfuck code into MovDBz. The Haskell implementation is available on Github, but be aware that it is somewhat-horrible spaghetti code.

One nice aspect of it, though, is that the compiler generates semantic labels and registers (like Cell i for the register containing the i'th Brainfuck cell, or ScanFinished i (Inc l) for the label of the instruction that starts incrementing the Cell i and eventually goes to label l when finished). This can make the output almost readable... For example, here's the result of compiling -.>. with two Brainfuck cells:

λ> mapM_ print $ compileBF 1 [DecData, Output, IncPtr, Output]
 (Src 0,MOVDBZ C0 C0 (S (Scan 0 (Dec (Src 1)))) (S (Scan 0 (Dec (Src 1)))))
 (Src 1,MOVDBZ C0 C0 (S (Scan 0 (Print (Src 2)))) (S (Scan 0 (Print (Src 2)))))
 (Src 2,MOVDBZ C0 C0 (S (DoIncPtr (Src 3))) (S (DoIncPtr (Src 3))))
 (Src 3,MOVDBZ C0 C0 (S (Scan 0 (Print (Src 4)))) (S (Scan 0 (Print (Src 4)))))
 (Src 4,HALT)
 (S (Scan 0 (Dec (Src 1))),MOVDBZ Ptr Tmp (S (ScanFinished 0 (Dec (Src 1))))
                                          (S (Scan 1 (Dec (Src 1)))))
 (S (Scan 0 (Print (Src 2))),MOVDBZ Ptr Tmp (S (ScanFinished 0 (Print (Src 2))))
                                            (S (Scan 1 (Print (Src 2)))))
 (S (Scan 0 (Print (Src 4))),MOVDBZ Ptr Tmp (S (ScanFinished 0 (Print (Src 4))))
                                            (S (Scan 1 (Print (Src 4)))))
 (S (Scan 1 (Dec (Src 1))),MOVDBZ Tmp Tmp (S (ScanFinished 1 (Dec (Src 1))))
                                          (S End))
 (S (Scan 1 (Print (Src 2))),MOVDBZ Tmp Tmp (S (ScanFinished 1 (Print (Src 2))))
                                            (S End))
 (S (Scan 1 (Print (Src 4))),MOVDBZ Tmp Tmp (S (ScanFinished 1 (Print (Src 4))))
                                            (S End))
 (S (ScanFinished 0 (Dec (Src 1))),MOVDBZ C0 C0 (S (DecCell 0 (Src 1)))
                                                (S (DecCell 0 (Src 1))))
 (S (ScanFinished 0 (Print (Src 2))),PRINT (Cell 0) (Src 2))
 (S (ScanFinished 0 (Print (Src 4))),PRINT (Cell 0) (Src 4))
 (S (ScanFinished 1 (Dec (Src 1))),MOVDBZ C0 C0 (S (DecCell 1 (Src 1)))
                                                (S (DecCell 1 (Src 1))))
 (S (ScanFinished 1 (Print (Src 2))),PRINT (Cell 1) (Src 2))
 (S (ScanFinished 1 (Print (Src 4))),PRINT (Cell 1) (Src 4))
 (S (DecCell 0 (Src 1)),MOVDBZ (Cell 0) (Cell 0) (S (UnderflowCell 0 (Src 1))) (Src 1))
 (S (DecCell 1 (Src 1)),MOVDBZ (Cell 1) (Cell 1) (S (UnderflowCell 1 (Src 1))) (Src 1))
 (S (UnderflowCell 0 (Src 1)),MOVDBZ CMaxData (Cell 0) (S End) (Src 1))
 (S (UnderflowCell 1 (Src 1)),MOVDBZ CMaxData (Cell 1) (S End) (Src 1))
 (S (DoIncPtr (Src 3)),MOVDBZ CMaxAddr Tmp (S (DoIncPtrLoop (Src 3) IncPtrDecCounter))
                                           (S (DoIncPtrLoop (Src 3) IncPtrDecCounter)))
 (S (DoIncPtrLoop (Src 3) IncPtrDecCounter),MOVDBZ Tmp Tmp (Src 3) (S (DoIncPtrLoop (Src 3) IncPtrDecPtr)))
 (S (DoIncPtrLoop (Src 3) IncPtrDecPtr),MOVDBZ Ptr Ptr (S (DoIncPtrLoop (Src 3) IncPtrUnderflowPtr))
                                                       (S (DoIncPtrLoop (Src 3) IncPtrDecCounter)))
 (S (DoIncPtrLoop (Src 3) IncPtrUnderflowPtr),MOVDBZ CMaxAddr Ptr (S (DoIncPtrLoop (Src 3) IncPtrDecCounter))
                                                                  (S  (DoIncPtrLoop (Src 3) IncPtrDecCounter)))
 (S End,HALT)

Which, after label and register layouting, comes out as this:

λ> mapM_ print $ layout 1 $ compileBF 1 [DecData, Output, IncPtr, Output]
(0,MOVDBZ 0 0 5 5)
(1,MOVDBZ 0 0 6 6)
(2,MOVDBZ 0 0 25 25)
(3,MOVDBZ 0 0 7 7)
(4,HALT)
(5,MOVDBZ 3 4 11 8)
(6,MOVDBZ 3 4 12 9)
(7,MOVDBZ 3 4 13 10)
(8,MOVDBZ 4 4 14 29)
(9,MOVDBZ 4 4 15 29)
(10,MOVDBZ 4 4 16 29)
(11,MOVDBZ 0 0 17 17)
(12,PRINT 5 2)
(13,PRINT 5 4)
(14,MOVDBZ 0 0 18 18)
(15,PRINT 6 2)
(16,PRINT 6 4)
(17,MOVDBZ 1 4 19 19)
(18,MOVDBZ 1 4 22 22)
(19,MOVDBZ 4 4 1 20)
(20,MOVDBZ 5 5 21 19)
(21,MOVDBZ 1 5 19 19)
(22,MOVDBZ 4 4 1 23)
(23,MOVDBZ 6 6 24 22)
(24,MOVDBZ 1 6 22 22)
(25,MOVDBZ 2 4 26 26)
(26,MOVDBZ 4 4 3 27)
(27,MOVDBZ 3 3 28 26)
(28,MOVDBZ 2 3 26 26)
(29,HALT)