A demonstration of a working 4-bit Brainfuck interpreter built inside the puzzle game SpaceChem, proving its Turing completeness.
I'm a winner! And yes, as Zach wrote there, I'm in parts responsible for the existence of the sandbox mode, which makes me even happier:
zachtronicsindustries.com/playing-in-the-sandbox-the-winners…
And now featured on Rock, Paper, Shotgun, the site that made me familiar with SpaceChem in the first place. Thanks, guys!
rockpapershotgun.com/2012/01/24/smashing-atoms-in-spacechems…
*** See the Detail videos to learn how it works ***
*** (activate annotations) ***
This is my entry for the sandbox contest, which closed on 1.1.2012. It is a working computer that executes brainfuck commands. SpaceChem is Turing complete!
Just a short demonstration. No clue what brainfuck is?
en.wikipedia.org/wiki/Brainfuck
Only differences: It works on nibbles (4 bit) instead of bytes. And going to the left from cell 0 may behave strange, but that is not needed anyway.
(I can't type the program shown here, youtube doesn't take those special signs.) Program gets two inputs, to the first and second memory cell, then adds the first to the second, then prints the result. It then ends, which means it jumps to the IO reactor, which shows the program has ended by running endlessly into a pause, carrying the Sigma token. You see me leave the reactor then, to have a longer look at the output.
Program encoding is a little complicated, I folded 6 commands into 4 inputs. P1 to P3 are one command, entering P4 before one of them switches to the second variant, e.g. switch Add to Subtract. This is done in the reactor in the lower left corner, fusion the first and third atom of the command with H.
P5 is loop start, P6 is loop end; P7 is a cluster of token needed in the system: memory end, sub command token (flow control, I'll explain that in detail somewhere else) and program end.
P8 is the uninitialised data token. Each column is a bit, it is 1 if I is on top. So the upper row shows the current value of the data item.
Short overview of reactors: Upper row has the functions lined up: flow control, input and output, increase operation, decrease operation, memory operations. Everything under that is subsystems of the reactors they're linked to. Commands run through the upper line followed by the current data item (in brainfuck terms, the currently pointed-to memory cell).
Took about 60 hours in SpaceChem, but occupied my mind over a month.
