When I came across a page about Brainf*** (which I prefer to call BF) written by
Urban Mueller, I immediately
felt in love with the language.
BF is a very minimalistic language, with only
eight commands, yet it is (theoretically) powerfull enough to compute
anything that can be computed (with a Turing Machine).
The language operates on an array of memory cells each containing an
initially zero integer value. There is a memory pointer which initially
points to the first memory cell. Each of the eight commands consists of
a single ASCII character, with the following meaning:
All commands are executed sequentially, except when specified differently.
Other characters are skipped, thus considered as comments. The execution
terminates when the end of the program is reached.
- '>' : move the memory pointer to the next cell,
- '<' : move the memory pointer to the previous cell,
- '+' : increment the memory cell under the memory pointer,
- '-' : decrement the memory cell under the memory pointer,
- ',' : fills the memory cell under the memory pointer with the
ASCII value of next character from the input,
- '.' : writes the contents of the memory cell under the memory pointer
as a character with the corresponding ASCII value,
- '[' : moves to the command following the matching ']', if the
memory cell under the memory pointer is zero, and
- ']' : moves to the command following the matching '[', if the
memory cell under the memory pointer is not zero.
I haven't found any definitive statement about the range of integer
values that can be stored in each memory locations. The original
interpreter by Urban uses bytes, that is values in the range 0..255,
but others have used other ranges. Personally, I prefer to use
all of the natural numbers, as that seems to be the most elegant choice
The language F
And just when you thought that BF is the most minimal language, someone
comes up with the language F,
which has only Boolean values for the memory cells, and proofs that it
is just as powerful as BF by providing a BF to F translator and giving
alternative proofs for F being Turing Complete. But then you also discover
that this result was already known in 1964.
Corrado Böhn created
the language P''
similar to F and proved that it was Turing complete.
home and email