# 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 a_{1}a_{2}...a_{n} where a_{i} denote RBF commands. Take any initial tape state and head position denoted by t_{0}.

If A halts on t_{0} and leaves the machine in state t_{1}, then A' := a_{n}'a_{n-1}'...a_{1}' halts on t_{1} and leaves the machine in state t_{0}. Here a_{i}' denotes the inverse of a_{i} 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 := a_{1}a_{2}...a_{x}, B := b_{1}b_{2}...b_{y}, C := c_{1}c_{2}...c_{z}, 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 }.