Reversible Bitfuck

Reversible Bitfuck (RBF) is yet another Brainfuck variant discovered by User:Orby in 2017. RBF was constructed as a target for minimization via simple translations.

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

Algebraic structure

Take an arbitrary RBF program A consisting of the string of symbols a₁a₂...a_n where a_i denote RBF commands. Take any initial tape state and head position denoted by t₀.

If A halts on t₀ and leaves the machine in state t₁, then A' := a_n'a_n-1'...a₁' halts on t₁ and leaves the machine in state t₀. Here a_i' denotes the inverse of a_i which translates thusly

Command	Inverse
*	*
>	<
<	>
(	)
)	(

Or, in abstract terms, we say that RBF programs form a group.

Every group can be seen as a monoid with equivalences which represent the inverse words. In particular, RBF can be considered a quotient of the monoid:

R₀ := <{ +, >, <, (, ) } | "" ≈ "++" ≈ "<>" ≈ "><" ≈ "()">

R₀ contains the obvious nops in RBF, but there are other equivalences in RBF which are not included. We can show that:

Theorem. r(R₀, { +, >, <, (, ) }*) ≤ 3. (Orby, 2020)

This is shown by considering the following monoid with rank ≤ 3:

M := < { +>, <(, ) } | "" ≈ "++" ≈ "<>" ≈ "><" ≈ "()">

Obviously, every word in M can be spelled with R₀. Additionally, every word in R₀ can be spelled with the following words in M (whitespace added for readability):

"+> <( )" ≈ "+ >< ()" ≈ "+"
"+> <( ) +>" ≈ "+ >< () + >" ≈ "++ >" ≈ ">"
"<( )" ≈ "<"
"+> <( ) +> <(" ≈ "+ >< () + >< (" ≈ "++ (" ≈ "("
")"

so M and R₀ are equivalent, and r(R₀, { +, >, <, (, ) }*) = r(M, { +>, <(, ) }*) ≤ 3.

This fact motivated the development of Nanofuck.

Simple translations

There is a simple translation from RBF to Nanofuck given by the following translation table:

RBF	NF equivalent
+	*{}
>	*{}*
<	{}
(	*{}*{
)	}

NF	RBF equivalent
*	+>
{	<(
}	)

The minimal equivalence relation required to make this work for RBF is "" ≈ "++" ≈ "()" ≈ "><", as shown in the following table:

from RBF	to NF	to RBF again
+	*{}	+><()
>	*{}*	+><()+>
<	{}	<()
(	*{}*{	+><()+><(
)	}	)

Notice that if { A, B, C } is a simple translation of RBF where A := a₁a₂...a_x, B := b₁b₂...b_y, C := c₁c₂...c_z, then { A', B', C' } is also a simple translation of RBF because of reversibility. We will call { A', B', C' } the dual of { A, B, C }.

See also

• Picofuck is a project to discover 2 command variants of RBF.
• Reversible Brainfuck
• Boolfuck

External resources

• rbf-lang - Reversible Bitfuck interpreter on GitHub. Implemented in Python.