Reversible Bitfuck

From Esolang
Jump to navigation Jump to search

Reversible Bitfuck (RBF) is yet another Brainfuck variant discovered by User:Orby in 2017.


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 -
< <
> >
( +[+
) +]+
*(* [
*)* ]


RBF enjoys a number of interesting properties.


Take an arbitrary RBF program A consisting of the string of symbols 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
* *
> <
< >
( )
) (


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 :=, B :=, C :=, 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