Immutable Brainfuck

Immutable Brainfuck is an esoteric programming language and a brainfuck derivative created by User:Rainwave in 2026. It was created to demonstrate the idea of monotonic computation, something that Rainwave has had in mind ever since he created Leafuck, as well as to create a language that satisfies both monotonicity and reversibility at once.

Language Semantics

Like brainfuck, the language operates on a right-unbounded tape, where the initial cells are all 0. Unlike brainfuck however, the commands cannot modify existing cells. Instead, new cells are dynamically inserted in the middle of the tape. A pointer is initially set to point to the first cell.

Immutable Brainfuck has the following commands

Command	Description
>	Move the pointer right by one cell.
<	Move the pointer left by one cell. If the pointer is currently at the first cell, the result is an undefined behavior.
[	If the current cell is 1, jump to the instruction after the matching ]. Note that this is slightly different from brainfuck where a loop is skipped if the current cell is 0.
]	If the current cell is 1, jump to instruction after the matching [.
1	Insert a new 1 cell right after the current cell.
0	Insert a new 0 cell right after the current cell.
.	Read eight contiguous cells starting from the current cell, interpret them as a byte, and output them as a single ASCII character. Note that the pointer's position remains unchanged.
,	Read an ASCII character from the input stream. Then, insert eight new cells right after the current cell, containing the character's binary representation. EOF is treated as the value 0.

All characters other than the symbols listed above are ignored. If the brackets ([ and ]) are not balanced, the program contains a syntax error.

Examples

Hello World!

0>1>0>0>1>0>0>0<<<<<<. 0>1>1>0>0>1>0>1<<<<<<. 0>1>1>0>1>1>0>0<<<<<<. 0>1>1>0>1>1>0>0<<<<<<. 0>1>1>0>1>1>1>1<<<<<<. 0>0>1>0>0>0>0>0<<<<<<. 0>1>0>1>0>1>1>1<<<<<<. 0>1>1>0>1>1>1>1<<<<<<. 0>1>1>1>0>0>1>0<<<<<<. 0>1>1>0>1>1>0>0<<<<<<. 0>1>1>0>0>1>0>0<<<<<<.

Shorter one by User:Blashyrkh:

0010100011000010100100111001101110100111111110111111011110000010100110101111101110011011100110111101001110001001[0>.>>>>>>>>]

Truth Machine

,>>>>>>>>[1]>[0>0>1>1>0>0>0>1<<<<<<.1>]0>0>1>1>0>0>0>0<<<<<<.

Shorter one by User:Blashyrkh:

,>.>>>>>>>[1]>[<<<<<<<<.>>>>>>>1>]

Reversibility

Immutable Brainfuck is reversible in the sense that at any state of the execution, it is possible to uniquely determine the previous state or to determine if the previous state was invalid. This is because each command has an inverse that can undo its effect when running the machine backwards.

Command	Inverse
>	Move the pointer left by one cell. If the pointer is currently at the first cell, the machine has evolved from an invalid state.
<	Move the pointer right by one cell.
[	If the current cell is 1, jump to the instruction before the matching ].
]	If the current cell is 1, jump to the instruction before the matching [.
1	Delete the next cell if its value is 1. Otherwise, the machine has evolved from an invalid state.
0	Delete the next cell if its value is 0. Otherwise, the machine has evolved from an invalid state.
,	Delete eight contiguous cells after the current cell.

Computational class

Immutable Brainfuck is Turing complete as Bitwise Cyclic Tag can be compiled into it. The following translation does not use the 0, ., and , commands, meaning the language can be simplified to just five commands while still retaining Turing completeness.

We will segment the tape into the following sections

[DELETED][DATA first][DATA middle][DATA last][EMPTY]

Each element in the data queue is represented with a block of cells as follows

0 = 10 NEXT PREV
1 = 01 NEXT PREV

The values of NEXT and PREV depend on the element's position in the data queue.

	First	Middle	Last
NEXT	1101	101	01
PREV	1011	101	10

Assuming the pointer is normalized at the first cell of the first element, each of BCT's three commands can be mapped as follows

Command	Mapping
0	>>>>>>>>>> >1>>>>>>1<<<<<<<
11	[>>>>[>>>>>>>>]<1>>>>>1> >1>>1>1>>[<<<<<<<<]<<<<<<<]
10	[>>>>[>>>>>>>>]<1>>>>>1> 1>>>1>1>>[<<<<<<<<]<<<<<<<]

Note: This construction assumes that the data queue will always have at least three elements. However, that might not always be the case, and the resulting behavior will be incorrect. It is possible to fix this by adding two dummy elements and treating the third element as the actual first element. This construction also does not consider halting, but that is not needed to prove the language Turing complete.

Implementations

Python

Talk:Immutable_Brainfuck#Interpreter

C++

Immutable Brainfuck/C++ Interpreter

Online interpreter based on the C++ interpreter.

See also

• Leafuck
• Reversible Brainfuck