Imagine a box of mints. If you want to feel fresh, you can take out a mint and have it. When the box is empty, you can refill it, or buy another box. Those boxes are like registers: places that hold a number of something. Register machines are made up of one or more of these registers, and can manipulate their content when we instruct them to. They are one of the simplest model for computation, and yet, capable of computing anything that can be computed with just a handful of instructions. For anyone thinking computing is complicated: it's not. What's fascinating is seeing how complex behaviors can be built (emerge?) from a tiny set of instructions, and register machines are a great reminder of that. So much so that after playing with register machines for a while, you will start to see computers everywhere! This document is a little introduction to register machines for people who don't know what they are. It uses nspace, a language with 6 core commands: n(ext) s(ubtract) p(rev) a(dd) c(opy) e(xec). This document is written as a series of questions and answers. The best way to learn from it is to read the question, think of your answer, then read the provided one. Make sure you write the programs as you go along, either using pen and paper or nspace-web. Read sequentially from the top and dont skip any step! If you're ready, let's get started.
what does a do? |
it adds 1 to the register. |
what does s do? |
it subtracts 1 from the register. |
| what happens when we subtract 1 to 0? |
nothing. A register holds a non-negative integer. |
| how can we add 13 to the register? |
aaaaaaaaaaaaa |
| can you think of a better way? |
maybe 13a? |
| yes! you can prefix each command with a number to tell it how many times it should repeat itself. |
|
what does n do? |
it moves the cursor to the next register. |
what about p? |
it moves the cursor to the previous register. |
| write a program that increases the first two register by 13 |
13an13a |
| Great. How about one that increases the first 8 registers by 13? |
13an13a13an13a13an13a13an13a13an13a13an13a13an |
| can you think of a better way? |
maybe 8(13an)? |
| yes! you can prefix a group of command enclosed in parenthesis with a number to tell it how many times it should repeat itself. Kuddos for writing a rot 13 program! |
|
what's 20n? |
it's sets cursor to 4, which is 20%16. |
| explain? |
because there are 16 registers. The next register after the 16th is the first. |
what does { do? |
it moves to the next command if the register is not 0, else it jumps to the next }. |
what does } do? |
it jumps back to the previous { if the register is not 0, else moves to the next command. |
| what can we compute using only the commands we've seen so far? |
everything, it's turing complete. Thank you Minsky (1961, 1967) and Lambek (1961). |
| write a program that adds the first register to the second. |
that may be a little difficult. Let's take it step by step. |
| describe in your own words what we should do if we want to add 2 to 3 |
we should a to 3 two times. |
you've identified the a part. How about the "two times"? |
we can use parenthesis, but that would make our program limited. Instead, we should use { and }. |
| correct! Where should cursor be when we start our program? |
it should be on the first register, which contains two, because we want to loop two times. |
right. And where should cursor be when we execute the } command? |
it should be on the first register, which acts as a counter for our loop. |
| describe in your own words what we should do if we want to add 2 to 3 |
we should start on the first register. If not zero, we subtract one, move to the next register, add one, go back to the previous register and loop back until we reach 0. |
| write a program that adds the first register to the second. |
how about {snap}? |
| snappy! |
|
what does v do? |
v tells the command to repeat itself as many times as the value of the register. |
| how can you double the value of the register? |
we can do va, which will add 1 to the register v times. |
what's va when the value of the first register is 1? |
2, because 1+1=2. |
what's va when r0=2? |
4, because 2+2=4. |
what's va when r0=4? |
8, because 4+4=8. |
what does k do? |
k tells the command to repeat itself as many times as the value of the cursor. |
what's ka when the value of cursor is 0 and r0=2? |
2, because 0+2=0. |
what's ka when k=1 and rk=2? |
3, because 1+2=3. |
what's ka when k=4 and rk=3? |
7, because 4+3=7. |
what does c do? |
it copies the value of the register at rk into rk. |
| how would you write a program that copies r(k-1) into rk? |
we first set rk to k-1, the use c. |
| write a program that copies r(k-1) into rk. |
kasc |
describe what this program does: an8(kascvan) |
it adds 1 to r0, moves k to the next register and starts a loop with 8 iterations. |
| what happens on the first iteration? |
we copy 1, the value of k-1 into rk, double it to 2 and move k to the next register. |
| what happens on the second iteration? |
we copy 2, the value of k-1 into rk, double it to 4 and move k to the next register. |
| what happens on the third iteration? |
we copy 4, the value of k-1 into rk, double it to 8 and move k to the next register. |
| what happens on the fourth iteration? |
we copy 8, the value of k-1 into rk, double it to 16 and move k to the next register. |
| what happens on the fifth iteration? |
we copy 16, the value of k-1 into rk, double it to 32 and move k to the next register. |
| what happens on the sixth iteration? |
we copy 32, the value of k-1 into rk, double it to 64 and move k to the next register. |
| what happens on the seventh iteration? |
we copy 64, the value of k-1 into rk, double it to 128 and move k to the next register. |
| what happens on the eighth iteration? |
we copy 128, the value of k-1 into rk, double it to 256 and move k to the next register. |
| what is this sequence? |
the power of two sequence! |
| how do we build a new number in a Fibonacci sequence? |
we sum the two numbers that precede it. |
| how would you write a program that copies the number at k-2? |
ka2sc |
| how would you write a program that copies the two preceding numbers? |
2(kas2scn) |
| write a program that prints the first 8 numbers of the Fibonacci sequence. |
nan 8(2(ka2scn)p{span}) |
| ready for the next sequence? |
I'll get a mint first! |
what does A do? |
it adds 1 to the register of the second dimension. |
so what does S do? |
it subtracts 1 from the register of the second dimension. |
| what's a dimension? |
a cursor and some registers. |
| how can you tell a command operates on d2? |
it use uppercase letters. |
| what do we call a machine with registers that can be randomly accessed? |
a Random-access machine! |
what does vA do? |
it adds 1 do the register of d2 v times, with v being the number stored in rk. |
| write a program that adds the first and second register of d1 to the first register of the d2 |
how about vAnvA? |
| Great! Now write a program that sums the first 5 registers of d1 to R0 |
5(vAn) |
what does v(nvAp) do? |
let's break it down! |
what does v(...) do? |
it executes the group of command v times. |
what does nvAp do? |
it moves to the next register in d1, adds v to R0 and goes to the previous register in d1. |
what does v(nvAp) do? |
it multiplies r0 by r1 in R0. |
| you got it. Now write a program that multiplies a register by itself. |
we can just use v(nvAp) and make sure r0=r1. |
do you remember what's va when r0=2? |
4, because it adds 2 to 2. |
what's 2(va) when r0=2? |
8, because it first adds 2 to 2, which is 4, then adds 4 to it. |
| how would you write 2^6? |
we set r0 to 2 and run 5(va) |
why not 6(va)? |
because we already start with 2 in our register. |
| how do you write 6 in binary? |
110, why do you ask? |
| we're about to write a program that converts binary to decimal! |
can I get a coffee first? |
| Are you back? |
yes. |
| write the little-endian version of 6 in binary. |
01100000 |
| in your own words, describe how a program could convert this to decimal. |
we go over each of the 8 digits. If it's one, we change it to 2^k and move k to next register. After the loop, we sum the last 8 digits. |
| write this program |
seems a bit difficult. |
| let's start with the first part. How can we "go over each of the 8 digits"? |
8(...n) |
| yes. Next, how do we check if the digit is 1? |
we can do{...}, but we'd be stuck in a loop unless we set the register back to 0... |
you're right... can you guess what [ and ] do? |
they are just like { and } but check d2's register. |
| how could we break out of the loop without setting d1's register back to 0? |
we could use ], since the register in d2 is 0. |
you mean something like that: 8({...]n)? |
you read my mind. |
| how can we change the register to 2^k? |
k(va) |
fill the blanks: 8({...]n) |
8({k(va)]n) |
| great! Now, we need to write this part: "After the loop, we sum the last 8 digits". How? |
we can loop back and sum each register in d2: k(pvA) |
yes. Here's your code so far: 8({k(va)]n)k(pvA). How can you simplify it? |
We can start filling an accumulator as we iterate over the first 8 registers. We just need to be careful that we target a blank register when we execute ]. |
| write the optimized version. |
8(N{k(va)]PvAn) |
| you are getting the hang of it! |
I sure am. |
| how do you test if r0 is not zero? |
we could use the { command. |
| write a program that sets R0 to 1 if r0 is true |
{An}. When r0 is not zero, we add 1 to R0 and move k to the next register, so that we can exit the loop. |
| how do you test if r0 is zero? |
could we first try to get NOT r0, and see if it's not zero? |
| sounds like a plan, how could we do that? |
we can first set r1 to true, then if r0 is true, set r1 to false. |
| write a program that computes NOT r0 in r1 |
nap{ns} |
| great! You know what's next. |
what is it? |
| write a program that sets R0 to 1 if r0 is false |
ok, so first we do NOT, then we test if not true: nap{ns}n{An}. |
| isn't it a little convoluted? |
a turing tarpit! |
we might be able to branch off the tarpit if we use the command |. |
what does it do? |
you should try it. Here's a program: {|An}. Does the result look familiar? |
it sets R0 to 1 if r0 is false. |
can you describe with your own words what happens when {|An} is executed? |
we check if r0 is not null. It's null in our case, so we jump directly after |. We add 1 to R0 and move k to the next register. We branched off the tarpit! |
| describe how we could write a program that sets R0 to 1 if r0 is greater than 10. |
we subtract 10 to r0 and set R0 to 1 if r0 is not empty. |
| write the greater than 10 program |
10s {An} |
| describe how we could write a program that sets R0 to 1 if r0 is less than or equal to 10. |
we subtract 10 to r0 and set R0 to 1 if r0 is empty. |
| write the less than or equal to 10 program |
10s {vs|An} |
| let's talk about equal! |
I'm ready. |
| write a program that sets R0 to 1 if r0 is equal to 10 |
do you have any tips? |
| how could you write this program only in terms of greater than and less than or equal? |
I could first check if r0 is greater than 9, and then test if that value is less than or equal to 1. |
| write the equal to 10 program |
9s { s { vs | An } } |
| I think we've got all we need for our next stop! |
lot of branches. |
what does : do? |
it lets you declare a procedure. |
what does ; do? |
it lets you return from a procedure. |
| how do you execute the first procedure you've defined? |
we make sure our register contains 0, and run the e command. |
| how do you execute the second procedure you've defined? |
we make sure our register contains 1, and run the e command. |
| you know everything! Now write a program that implements the elementary cellular automaton rule 30. |
excuse me!? |
| what's an automaton? |
some machine that can transition to a finite number of states. |
| what's a cellular automaton? |
it's an automaton with cells whose transition table depend on the state of their neighbouring cells. Thank you Stanislaw Ulam and John von Neumann. |
| what's a elementary cellular automaton? |
a cellular automaton with a single dimension, and where each cell can be in two states: 0 or 1. Thank you, Stephen Wolfram. |
| how many neighbours does a cell have in an elementary cellular automaton? |
two. |
| how many configuration can there be for a cell and its neighbors? |
2^3=8, because each cell can be either 0 or 1, and has 2 neighbors. |
| a rule is a complete specification of how any cell should evolve based on its neighborhood configration. Because there are 8 configuration, how many rules are there? |
2^8=256 possible rules, because each configuration can be either 0 or 1 in the next generation. |
| what is rule 30? |
it's the rule with the Wolfram code 30. |
| and what's that? |
it's a scheme that encode rules for elementary cellular automa. Each configuration is written in this order: 111, 110, 101, 100, 011, 010, 001, 000. The resulting state is written as a base 10 integer. 30 = 00011110. |
| with your own words, describe how you could write a program that takes a single integer from 0 to 7 and output the corresponding value from rule 30. |
we could look at r0. We would then need some sort of switch statement. |
| how would you make a switch using procedures? |
we could create 8 procedures. Then it would only be a matter of using the execute command to call the correct one based on the number in the register. |
| let's do it! |
:VS; :VSA; :VSA; :VSA; :VSA; :VS; :VS; :VS; |
| great. However the code of the procedures gets executed when we run the program, even if we don't call it. Why is that? |
because we haven't surrounded it by brackets. This should fix it: [:VS; :VSA; :VS; :VSA; :VSA; :VS; :VSA; :VS;] |
| if we have 4 in r0, how do we get the value of 011? |
we just use the execute command, as such: e. That's because 011 is 3, and we're calling the 3rd procedure we've defined. |
| perfect. Next, we're going to use d2 to draw the time-space diagram of our automaton. Each group of 16 registers will be a generation. Write the first generation with a single 1 cell in the middle. |
8NA8NA should do it. |
| describe with your own words how you could write a program that computes the first 8 generations of this automaton. |
we need to loop 8 times to compute 8 generations. In each loop, we copy the previous generation to d1 and compute the next state of each of its 16 cells in d2. |
| let's start with "we need to loop 8 times to compute 8 generations" |
simple enough: 8(...) |
what does 16P16(vsVanN) do? |
first it rewinds d2's cursor back a generation, then copies that generation in d1. |
yes! now, what does 16(...EN) do? |
it loops 16 times. For each iteration, it executes the procedure whose value is in the current register of d2, then moves to the next register in d2. |
| can you guess what the missing part is? |
that's where we compute the next state of the cell based on its neighbors. |
| how can we do it? |
we need to go back one cell and get the value of the following 3 bits. We then need to place that value in the current register of d2. |
so something like pv(4A)nv(2A)nvA |
exactly what I was thinking! |
| I think we have all the parts. Can you write the whole program? |
# Rule 30
[
:VS; :VSA; :VSA; :VSA; :VSA; :VS; :VS; :VS;
]
8NA8N
8(
16P16(vsVanN)
16(pv(4A)nv(2A)nvAEN)
)
|
| what shall we do then? |
let's run it! |
| what pattern do you see on the time-space diagram? |
a bit chaotic |
| rule 30 is know to be unpredictable and chaotic. It has even been used for random number generators! |
it should be used for decoration. |
| now, let's look at rule 90. What's 90 in binary? |
01011010 |
| if that was used for a truth table, which operator would it be for? |
it's 1 only when a single neighbor is 1, but 0 otherwise. Looks like an exclusive or. |
| yes. Rule 90 replace each cell of the previous generation by the XOR of their neighbors. |
I see. |
| what change to our program would you need to do to implement rule 90? |
we would only need to change the procedures. Everything else stays the same. |
| yes. Could you do it? |
# Rule 90
[
:VS; :VSA; :VS; :VSA; :VSA; :VS; :VSA; :VS;
]
8NA8N
8(
16P16(vsVanN)
16(pv(4A)nv(2A)nvAEN)
)
|
| what pattern do you see on the time-space diagram? |
triangles within triangles. |
| thank you Sierpiński. |
what are other interesting rule? |
| Can you implement rule 110? |
# Rule 110
[
:VS; :VSA; :VSA; :VSA; :VS; :VSA; :VSA; :VS;
]
8NA8N
8(
16P16(vsVanN)
16(pv(4A)nv(2A)nvAEN)
)
|
| what pattern do you see on the time-space diagram? |
I'm not sure. What is this rule about? |
| this rule is known as one of the simplest Turing complete system. |
so any calculation or program can be simulated using this automaton? |
| yes. Congrats on building a computer within a computer! |
computers are everywhere. |
You've now reached the end of this introduction. What are your options? You could try to write a 2d cellular automata and test different rules. You can make an nspace machine where some registers play a note, and make a song with it. You can try to connect two nspace machines together and make them interact through a designated register. You could write your own nspace interpreter with new commands or write a language that compiles into nspace. You can try to remember that computing anything that can be computed doesn't require a lot. Doesn't even require a computer. Just some mints in a box!