## From Register Machines to Brainfuck, part 2

This is a continuation of my previous post on register machines vs. Brainfuck programs. We left off at Brainfuck's supposed Turing-completeness.

Now, the most straightforward way to prove Turing-completeness of a given language is to write a compiler that takes a program written in a language that is already known to be Turing-complete, and creates a program written in the language to be proved Turing-complete, that simulates the original program. So an obvious way to prove that Brainfuck is a Turing-complete language is to compile register machine programs into Brainfuck. This has the added advantage that a programmer having some experience in real-world assembly programming can easily write register machine programs, which can then be compiled into (horribly inefficient and over-complicated, as we'll see) Brainfuck programs.

Important note: Of course, to really prove, in a mathematical sense, that Brainfuck is Turing-complete, we would first have to define formal operational semantics for register machines and Brainfuck programs to be even able to argue about simulating one with the another. In this post, I will appeal to intuition instead.

So how does one simulate a register machine (RM for short) using Brainfuck? The first idea is that since a given RM program can only reference a finite number of variables, we can lay them out in the linear array of memory cells provided by the Brainfuck model. So we can assign e.g. cell number #0 to a, #1 to b and #2 to z, and any operation working on z first increments the pointer twice (i.e. >> in Brainfuck notation), then does something, then decrements the pointer twice (<<) to get it back to the initial state. So for the line

clr z,

we can write

`>>[-]<<`

Similarly, we can compile

dec b

to

>-<

### Enter Loop

In fact, to make further work simpler, we can devise an intermediate language that has constructs similar to Brainfuck, but that uses named registers instead of a linear array. The language called Loop has the following statements:

• inc r, dec r, clr r
• while r stmts: Repeatedly execute the statements in the body as long as the value of r is non-zero.
• out r, in r

Once all the registers are laid out in the linear memory, compiling this to Brainfuck is trivial.

### From RM to Loop

As we've previously noted, the other major difference between RM and Brainfuck is that Brainfuck programs can't directly control their execution sequence. If your Brainfuck program contains "<++" at the next position, you can be 100% sure that the pointer will move left and then increment the cell twice, and there is nothing you can do about it. Contrast this with RM's jmp and jz instructions that can change the statement that gets executed next.

To reconcile this difference, the key idea is to start thinking about RM programs in a different way. Instead of a sequential list of instructions with possible jumps between, let's look at it as an n-ary branch switching on some special register called a Program Counter. So for the following program that adds a to b:

1. clr tmp
2. jz a 7
3. dec a
4. inc tmp
5. inc b
6. jmp 2
7. jz z 11
8. dec tmp
9. inc a
10. jmp 7
11. Done.

we can also imagine it as the following program, written in some unspecified pseudo-code:

```pc ← 1
while pc ≠ 11 loop
switch pc
case 1:
clr tmp
pc ← 2
case 2:
if a = 0 then
pc ← 7
else
pc ← 3
case 3:
dec a
pc ← 4
case 4:
inc z
pc ← 5
case 5:
inc b
pc ← 6
case 6:
pc ← 2
case 7:
if z = 0 then
pc ← 11
else
pc ← 8
case 8:
dec z
pc ← 9
case 9:
inc a
pc ← 10
case 10:
pc ← 7
end loop
```

At first glance, we don't seem to be any closer to our goal, since now we have to implement if and switch in Loop. First, let's observe that it makes no difference if several values of the pc register are handled in a single iteration of the outermost loop. Using this observation, and getting rid of some superfluous partitioning of statements, the above can be rewritten as the following:

```pc ← 1
while pc ≠ 11 loop
if pc = 1 then
clr tmp
pc ← 2
if pc = 2 then
if a = 0 then
pc ← 7
else
pc ← 3
if pc = 3 then
dec a
inc tmp
inc b
pc ← 2
if pc = 7 then
if tmp = 0 then
pc ← 11
else
pc ← 8
if pc = 8 then
dec tmp
inc a
pc ← 7
end loop
```

We've eliminated the need for switch, and all our if branches fall in one of the following two categories:

• Testing if the special register pc equals a given predeterminate value
• Testing if a given register is non-zero

The first kind of test we can simulate by using not just one pc register, but one for each possible value of pc, taking values of 0 or 1. So we enforce the invariant that pci is 1 iff the virtual pc register equals i. Then we can use while loops for branching by testing for pci and then immediately after, decrementing it, thus ensuring that the loop runs at most once. The above program thus becomes:

```dec pc11
inc pc1
while pc11 loop
while pc1 loop
dec pc1
clr tmp
inc pc2
end loop
while pc2 loop
if a = 0 then
inc pc7
else
inc pc3
end loop
...
while pc8 loop
dec pc8
dec tmp
inc a
inc pc8
end loop
end loop
```

Note the special handling of pc11 which gets decremented first, to -1, so that incrementing it later exits the main loop.

We are inching closer and closer to our destination – we just need a way to increment one of two pc registers based on the value of some other, non-pc register. Solving this requires some trickery because we can only use loops for testing if a given register is zero, but then we have to zero it out unless we want to get into an infinite loop. The solution is similar to what we do in our original adding example, by using a separate register as temporary storage. Suppose we want to translate the following piece of code:

```if a = 0 then
inc pc7
else
inc pc3
```

Using a temporary buffer, it is possible to run two loops that by the end preserve the register a's initial value, but allow us to change other registers in the process. We will use two special-purpose registers Z and NZ to signal if the value of a is zero or non-zero. First, we set up Z:

```inc Z
inc NZ
while a loop
dec a
inc Buffer
clr Z
end loop
while Buffer loop
dec Buffer
inc a
end loop
```

By that point, a retained its original value, but Z is 1 iff a is zero at the start. So now we can discriminate between the two cases using yet more loops:

```while Z loop
dec Z
inc pc7
dec NZ
end loop
while NZ loop
dec NZ
inc pc3
end loop
```

Note how the loop for Z decrements NZ, thereby preventing the other branch from running.

### Wrapping it up

We've now arrived at a valid Loop program, which can readily be translated into a Brainfuck program. I've implemented an RM Loop Brainfuck compiler using the above scheme in my Brainfuck toolbox.

One surprising aspect of the above is that the resulting Brainfuck program, while hideously complicated and large, doesn't perform that bad. Maya was kind enough to write a register machine program solving the 9-digit problem (source here), and I compiled it into x86 assembly via the Brainfuck route, to compare it with his native Brainfuck solution. Let's look at program size first: the native one is 4,591 instructions long, and the one compiled from RM comes in at a whopping 480,466 instructions. However, both implementations showed runtime performance in the same order of magnitude.

Unfortunately, I don't have a corpus of algorithms implemented in both RM and Brainfuck lying around, so I can't do any real benchmarks. But compared to my initial expectations, the result of the 9-digit program is promising: I figured this whole RM → Brainfuck compiler scheme would turn out to be a strictly theoretical result, creating Brainfuck programs that are so slow to be completely impractical.

Epilogue: I wanted to write some Agda-checked proofs that the compiler actually generated equivalent programs. As it turned out, this is not so easy. I hope I'll have time to get back to this problem soon.

### pandawill 2013-04-23 04:56:57

z The Pandawill an online store, operates various brands,a variety of a variety of large-screen smart phones and tablet PCs,and the necessities of life.iNew i3000

### the best china wholesale 2013-04-23 05:27:51

Y Tablets, smart phones, online sales, the cheapest electronic wholesale market, China - pandawill.comLenovo LePhone K800

### http://www.oakleywomenssunglasses.com/ (http://www.oakleywomenssunglasses.com/) 2013-04-28 09:00:16

We appreciate for sharing the good products with us. Without a pair of dark glasses, <strong>oakley womens sunglasses</strong> don't say you really understand fashion, even if you just used to play the model case, so what? In Europe and the star is not that right, no matter indoor or outdoor, <strong>Oakley Special Edition Sunglass sunglasses</strong> are always hand a big fly, want to know that the sunglasses Yu Mingxing, like in a girlfriend, in a quarterly is definitely not stingy.<br> For boys go sell of course,<strong> oakley sunglasses men</strong> the most popular, a big glasses. Romantic love in the film &quot;brokenhearted 33 days&quot;, the article plays wang, and he wears a black big glasses of restoring ancient ways is nifty and fashion. However, not everyone is suitable.<p href="http://www.oakleywomenssunglasses.com/" href="http://www.oakleywomenssunglasses.com/specials.html" href="http://www.oakleywomenssunglasses.com/products_new.html" class="STYLE1">Color too deep sunglasses will probably because of the traffic signal recognition and accidents, <strong>Oakley M Frame Sunglass </strong>poor ability of color too shallow sunglasses there is less than the role of keep out sunshine, at present only for red, green and yellow colors of sunglasses made strict rules traffic signal recognition ability, <strong>oakley mens sunglasses</strong> other color is not relevant provision, but there is a recruit, <strong>Oakley Batwolf Sunglass</strong> you might as well give it a try: when choosing sunglasses that is must try when buy, oakley sunglasses womens look around the environment change size color, color difference changes little sunglasses in general its color is more appropriate. As we all know, <strong>Oakley Asian Fit Sunglass</strong> sunglasses is the most one to one function is the uv protection.</p> cxf </br>

### ルイ・ヴィトン (http://www.louisvuitonshopjp.com) 2013-04-28 11:03:26

K The gradual improvement of living standards, demand for mobile phones is not limited to communications, is the pursuit of the appearance of the phone and entertainment properties, then in the end what kind of phone is able to meet all these requirements? Pandawill special launch lifestylish digital shopping guide series, holding a purse you accurate shot, to buy their favorite products. pipo tablet

### Kim Jeruk 2013-05-03 09:49:25

Thanks a lot for such a wonderful post, the stuff posted were really interesting and water softener indonesia

### Adidas Jeremy Scott 2013-05-13 10:32:53

Prefabricated storage equipments include loads of colorations, sizes along with prices. It is possible to have a simple twelve month period a something like 20 a 7 system intended for less than 5K, as well as the bigger 40' buildings may be about something like 20 -- 50K+. In comparison with classic engineering, they are extremely cheap selections. Loads of prefabricated storage equipments will not include the storage doorways, walk-through doors, masonry anchors, along with home windows, yet Cycling Sets can be bought intended for pay for on your own. Frequently, its most effective when you can set up the system on the bare cement piece. That provides for the most secure footing, yet seriously isn't the merely method. You might set up over diet property and also stones. The bare cement base possesses clear rewards and is particularly strongly suggested. When you have the foundation memorized it is possible to commence design along with assembly. Because continually, just make sure to check on nearby making constraints to be sure many will be nicely toying with starting. Even though these types of jerseys are generally originally planned for bike riders, various physical activities buffs are employing these types of jerseys because nicely. Also, these types of jerseys are generally perhaps utilised not simply for virtually every distinct physical activities occasions, yet inside any kind of out-of-doors action also. Cycling jerseys are additionally categorised as mountain bike jerseys. They are specifically created for individuals who perform a large number of cycling. The truth is, cycling jerseys aren't such as just simply virtually any everyday jerseys, considering that these types of jerseys are generally created specifically prolonged from the again. That Maillot Cyclisme Pas Cher will be really extremely simple intended for bike riders because the long-back style connected with cycling jerseys is perfect for the cyclist's decrease to continue being taken care of because they bends on the tackle icon connected with your mountain bike. In addition, specifically developed jerseys as a rule have hard drive budgets positioned on the again. Budgets intended for cycling jerseys are generally rationally positioned on the again since that makes things through spilling, because what is most probably to be able to occur if budgets are developing entrance.

### coach store online (http://www.chanluustore.org/) 2013-05-14 06:06:19

For some of us, the only chan luu bracelet we have. If that http://www.chanluustore.org/ familiar, it will be no problem staring this Marc Jacobs Sale in the face as you down your booze.Steve Madden's popular "MARC JACOBS" ankle strap heels are \$79.95 at stevemadden.com.Throughout the http://www.marcjacobssale.co.uk Marc Jacobs UK she wears tassel cheap coach purses and jewels with conch pearls, and at parties her flapper cheap coach purses is always completed with "The Marc By Marc Jacobs Clutch" - a headdress of diamonds and cultured marc jacobs handbdags, while daisy designed http://www.usitccoachpurses.net coach outlet store rings sit on her fingers.This is a http://www.marcjacobsbagsstore.com marc jacobs bags every woman raves about and I'm definitely an advocate of it. I use it to hydrate and protect my cheap coach purses as well as a hand marc by marc jacobs or to ease any bit of dry skin.chan luu may suffer accusations of nepotism from some quarters, but as we perch on a display case of the cheap coach purses store's stock, while random coach purses outlet pulsates in the background, I am afforded a close-up view of her http://www.voguecoachoutlet.com coach outlet online.With Mother's Day on Sunday, it's time to take a look back at our style-trailblazing cheap coach purses, past and present.

### UltraFire L2 2013-05-16 03:33:49

H I just wanted to comment on your blog and say I really enjoyed reading your blog here. It was very informative and I also digg the way you write! Keep it up and I'll be back soon to find out more mate.UltraFire L2

### Majuri 2013-05-18 07:18:11

Oh! So nice. You did really so wonderful job. You have posted very informative thing. I am excitedly waiting for you next post. glutera