Reversible Brainfuck

From Esolang
Jump to: navigation, search

Reversible Brainfuck is a brainfuck derivative created by User:ais523 at the end of 2006. It uses the same right-infinite tape starting with zeros as brainfuck does, and most of the same commands.

Commands

Six of the commands are identical to brainfuck.
+ Increment the current cell.
- Decrement the current cell.
> The cell to the right of the current cell becomes current.
< The cell to the left of the current cell becomes current.
. Output a character whose ASCII code is that of the current cell.
] If the current cell is nonzero, jump backwards to just after the matching [.
Two of the commands are changed.
, Input a character and store its ASCII code in the current cell, if it contains a 0. If the current cell doesn't contain a 0, end the program. EOF is treated as if a 0 were read.
[ If the current cell is nonzero, jump forwards to just after the matching ]. (In brainfuck, [ jumps forwards if the current cell is zero, but Reversible Brainfuck jumps forwards if the current cell is non-zero).

Compatibility

Reversible Brainfuck uses a right-infinite tape. Each cell on the tape must be able to be decremented 255 times from zero and incremented 255 times from zero without giving a zero result on any increment. (However, it's legal to use a wrapping system where, for instance, -128 and 128 are the same number.)

Computational class

The following reduction from ordinary brainfuck to Reversible Brainfuck proves that the latter is Turing complete. It ignores the special behavior of input on a non-zero cell.

To avoid the impossible deletion of information in a reversible language, the translation works by keeping a complete history of all branching.

Note that all non-brainfuck data cells will contain only values 0 or 1. Therefore this reduction can be applied to any cell size, even single bit cells. (E.g. this also proves Turing complete reversible boolfuck.)

Tape layout
Position Contents Description
0 0 Left boundary data search mark
1 0 Left boundary history search mark
2 d0 First brainfuck data cell
3 h0 First branch history flag
4n 1 Search marks to the left of current brainfuck data cell
0 Search marks to the right of current brainfuck data cell
4n+1 1 Search marks to the left of current branch history flag
0 Search marks to the right of current branch history flag
4n+2 dn Brainfuck data cell
4n+3 hn Branch history flag
Brainfuck command Reversible brainfuck
+
+
-
-
>
>>+>>
<
<<-<<
.
.
, , (with limitations)
[
[>>[<<<<]>[>>>>]<<
+>>[<<<<]<[>>>>]<<
]>>[<<<<]>[>>>>]<<
[>>+>>
 >>[<<<<]<[>>>>]<<
]
 >>[<<<<]>[>>>>]<<
+>>[<<<<]<[>>>>]<<
[>>[<<<<]>[>>>>]<<
->>[<<<<]<[>>>>]<<
]>>[<<<<]>[>>>>]<<
]>>+>>
 >>[<<<<]<[>>>>]<<

Implementations

weave.rb supports Reversible Brainfuck with the -r flag.

See also