Reversible Bitfuck
Reversible Bitfuck (RBF) is yet another Brainfuck variant discovered by User:Orby in 2017.
Definition
RBF is defined on a tape machine with 1-bit cells. The tape machine is unbounded on the right. It uses 5 commands.
| Command | Description |
|---|---|
| * | Toggle the current bit |
| > | Shift the tape head right |
| < | Shift the tape head left |
| ( | If the current bit is zero, jump past matching ) |
| ) | If the current bit is zero, jump to just after matching ( |
RBF is Turing complete by reduction to 1-bit Reversible Brainfuck which is known to be Turing complete. The simple translations to and from 1-bit Reversible Brainfuck are
| Reversible Bitfuck | 1-bit Reversible Brainfuck | |
|---|---|---|
| * | ↔ | + or - |
| < | ↔ | < |
| > | ↔ | > |
| ( | → | +[+ |
| ) | → | +]+ |
| *(* | ← | [ |
| *)* | ← | ] |
Properties
RBF enjoys a number of interesting properties.
Reversibility
Take an arbitrary RBF program A consisting of the string of symbols a1a2...an where ai denote RBF commands. Take any initial tape state and head position denoted by t0.
If A halts on t0 and leaves the machine in state t1, then A' := an'an-1'...a1' halts on t1 and leaves the machine in state t0. Here ai' denotes the inverse of ai which translates thusly
| Command | Inverse |
|---|---|
| * | * |
| > | < |
| < | > |
| ( | ) |
| ) | ( |
Minimization
RBF was constructed as a target for minimization. It is known that 3 command simple translations exist (see Nanofuck). Picofuck is the community project to discover 2 command variants which is thus far inconclusive. Notice that if { A, B, C } is a simple translation of RBF where A := a1a2...ax, B := b1b2...by, C := c1c2...cz, then { A', B', C' } is also a simple translation of RBF (see reversibility). We will call { A', B', C' } the dual of { A, B, C }.
See also
External resources
- rbf-lang - Reversible Bitfuck interpreter on GitHub. Implemented in Python.