Reversible BitFuck (RBF) is a reversible Turing tarpit. It is based on a tape of bits and has 5 commands:

• * 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 (

Here is an example program operating on 3 bits. Bit 0 is the source bit (x), bit 1 is the target bit (y) and bit 2 is the temporary bit (f). Here the value of x is being moved to y.

# x=?, y=0, f=0
(>>*<<)        # set f if x is set
>>(            # if f is set
    <(>*<)*    # set y
    <*(>>*<<)  # unset x
>>)
<(>*<)         # if y is set, unset f

we can run the above program on an example tape (100) with rbf cli:

rbf run -t 100 "(>>*<<)>>(<(>*<)*<*(>>*<<)>>)<(>*<)"  # outputs 010

Since RBF is reversible, we can easily create a move left program:

rbf reverse "(>>*<<)>>(<(>*<)*<*(>>*<<)>>)<(>*<)"  # outputs (>*<)>(<<(>>*<<)*>*(>*<)>)<<(>>*<<)

RBF can be installed from source with

pip install .

or from pypi with

pip install rbf-lang

(as of yet uncategorised links to related topics. Will be sorted and expanded in the future)

• https://en.wikipedia.org/wiki/Toffoli_gate
• https://arxiv.org/abs/1110.2574
• https://www.sciencedirect.com/science/article/abs/pii/016727899090185R?via%3Dihub
• http://weblog.raganwald.com/2004/10/beware-of-turing-tar-pit.html