Brainf*ck Turing Machine Interpreter

February 20th, 2020

+++.>+++++.[<+>-]<.

With comments

sum of two cells
+      cell(0) = 1
.      print
>      move to cell(1)
++     cell(1) = 2
.      print
[      go to matching bracket if this cell is non zero
    <  go back to cell(0)
    +  increment cell(0)
    >  go to cell(1)
    -  decrement
]      go back to matching bracket if this cell is zero
<.     print result
+++++.[-]++.

With comments

Replace the value of a cell
+++++. load a value
[-]     clear the cell
++++++. the new value
+++++. load a value

[
    - decrement
    > move
    + increment
    < go back
]
+++++.

[
    - decrement
    > move
    + increment
    > move
    + increment
    << go back
]
+++++. load 5

[->+>+<<] copy contents into a new cell
>>
[->
    +++ multiply by 3
<]
>. print result
swaps cell(0) and cell(1)
+++++.>++++++++.< load some values

[->>+<-<]
>[-<+>]
>[-<+<+>>]

The shortest known bf code to generate 42

--[>+<++++++]>-

Simpler code to generate 42. Compare this to the multiplications example. Do you see the trick?

>>++[-<+++[-<+++++++>]>]<<.
++++>+.>+<<[->>.[->+>+<<]>>[-<<+>>]<<<[->+<]>>[-<<+>>]<<<]>>.

With comments.

Fibonacci
number of iterations
++++ This program will print this many fibonacci numbers
plus the first two terms we initialize here
>
+. 1   (put 2 here for the Lucas numbers)
>
+  1
<<
start loop
[-
    copy second term
    >>.
    [->+>+<<]
    move copy to blank cell
    >>
    [-<<+>>]
    sum first and second terms
    <<<
    [->+<]
    move (old) second to first place
    >>
    [-<<+>>]
    go to first cell to restart loop
    <<<
]
>>. print last term

The Brainf*ck Language


Instruction Description
> Move the tape pointer to the right
< Move the tape pointer to the left
+ Increment the tape cell under the pointer
- Decrement the tape cell under the pointer
[ Jump past the matching right bracket if the cell under the pointer is 0
] Jump back to the matching left bracket if the cell under the pointer is nonzero
, Input a character and store it in the cell at the pointer
. Output the character signified by the cell at the pointer
Anything else Ignored

Brainf*ck Keywords

Adapted from esolangs.org

Brainf*ck (or BF) is one of the most famous "esoteric" programming languages. Invented in 1993 by Urban Müller, it was intentionally designed to be an extremely small language. The language consists of only 8 keywords meant to correspond to the behavior of a Turing machine. Every program starts on the first cell of an infinite tape of cells, and each cell can hold a value between 0 and 255. You can move the tape "pointer" left or right and increment or decrement the values in a cell. The most difficult part to get your head around is using the brackets ([ and ]) to repeat a block of code over and over again. But it is this ability to conditionally run a block of code which promotes BF from a language which just puts values in cells to a full-fledged Turing-complete programming language.

Notes


  • I opted for a "wrapping" implementation of brainf*ck, meaning that if you decrement a cell with a 0 in it, it will wrap around to 255. Similarly, if a cell contains 255, incrementing will cause it to wrap to 0.
  • In most implementations of BF, output is interpreted as the ascii encoding of a character. So for example, to print the character 'A', you need to increment a cell to 65, and then output with the "." instruction. However, I felt this would make even simple programs take far too long to animate, so, by default, output is just the literal number in a cell.
  • I had the idea to make a Turing machine interpreter for brainf*ck a while ago and couldn't find any examples of this online. Until, of course, right after I completed it. Here is a very similar page created by Fatih Erikli. He has some other really neat things on his page, so check it out!
  • In my Recursion Theory class, my teacher showed us a website which lets you play with Turing machines in a similar way. You can check it out at turingmachinesimulator.com.

Footnotes


  1. Compare this to languages like Java or C which have dozens of keywords.