# Brainf*ck Turing Machine Interpreter

February 20th, 2020

The shortest known bf code to generate 42

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

## The Brainf*ck Language

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.