Nanofuck

Nanofuck (NF) is a simple translation of Reversible Bitfuck (RBF) in 3 commands discovered in 2017 by User:Orby.

Definition

Machine

An NF machine is basically a Boolfuck machine. A tape model is used. The tape is unbounded on the right. A tape head moves to the right and left over the tape. Each cell on the tape is a single bit. The tape contents and initial position of the tape head are dependent upon input, but in the absence of input the tape should be initialized to zero and the tape head should point at the first cell. The content of the tape and the position of the tape head are considered output upon completion.

Commands

NF has 3 commands: *, {, and }.

Toggle/shift

*

The toggle/shift command toggles the current bit, then shifts the tape head to the right. It is equivalent to the C code

*tape = !*tape; tape++;

Loop

{ ... }

The loop semantics differ slightly from Boolfuck. This is in order to maintain reversibility. It is equivalent to the C code

tape--; if (*tape) do { ... } while (!*tape);

The algorithm is

1. Move the tape head to the left.
2. If the current bit is not set, then goto 5.
3. Execute the code between the braces.
4. If the current bit is not set, goto 3 (notice the difference).
5. Exit loop.

A similar convention is used in Reversible Brainfuck, though Reversible Brainfuck uses converse conditions.

Grammar

The grammar which generates valid NF programs can be written in Backus normal form as

 <exp> ::= <exp><exp> | "{" + <exp> + "}" | "*" | ""

Reversibility

To take the inverse of an NF program, reverse the program string and use following substitutions:

*       {}*{}
}       *{}*{
{       }*{}*

To simplify an NF program, remove all occurrences of the following sequences

*{}*{}
{}*{}*

Example

For example, the program

*{}

Reversed is

}{*

Using the aforementioned substitutions is

*{}*{}*{}*{}*{}

Simplified is

*{}

So this program is it's own inverse. This makes sense if we consider what the program does (it simply toggles the current bit).

Reversible Bitfuck

Most people will find it easier to program in the intermediate language Reversible Bitfuck (RBF). NF is a simple translation of RBF. By simple translation I mean there exist translation tables between NF and RBF with a single entry for each command in each table. Notice that the loop construct in RBF still differs from the loop construct in Boolfuck. RBF maps to and from NF in the following way:

From RBF to NF

+       *{}        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 after matching (

From NF to RBF

*       +>
{       <(
}       )

Inverting RBF code is trivial and will be left as an exercise to the reader. As a consequence of the reversibility of RBF, there exists a dual to NF which we will call NF'. It is defined in the following way:

From RBF to NF'

+      {}*
>      {}
<      *{}*
(      {
)      }*{}*

From NF' to RBF

*       <+
{       (
}       )>

Boolean functions

A Toffoli gate is a universal reversible logic gate. A Toffoli gate maps the inputs (A, B, C) to (A, B, C XOR (A AND B)). It is possible to express a Toffoli gate in NF, thus NF is capable of computing any Boolean function. Suppose we have three consecutive bits labeled A, B, and C. If the tape head is currently on A, then the NF code

*{}*{*{}**{}*{*{}**{}{}}{}}

computes the Toffoli gate. This has a much nicer representation in RBF

(>(>+<)<)

Additionally, here is a list of all classical logical connectives in RBF. Suppose we have three bits, 0, A, B and the tape head points at A. The following pieces of code will calculate the designated function and replace the 0 with it's output.

                                F
<+>                             T
(<+>)                           A
>(<<+>>)<                       B
+(<+>)+                         NOT A
>+(<<+>>)+<                     NOT B
(>(<<+>>)<)                     A AND B
<+>(>(<<+>>)<)                  A NAND B
<+>+>+<(>(<<+>>)<)+>+<          A OR B
+>+<(>(<<+>>)<)+>+<             A NOR B
>+<(>(<<+>>)<)>+<               A IMPLIES B
+(>(<<+>>)<)+                   B IMPLIES A
(>(<<+>>)<)+>+<(>(<<+>>)<)+>+<  A = B
+(>(<<+>>)<)+>+<(>(<<+>>)<)>+<  A XOR B
<+>>+<(>(<<+>>)<)>+<            NOT (A IMPLIES B)
<+>+(>(<<+>>)<)+                NOT (B IMPLIES A)

Miscellaneous code

Interesting code snippets in RBF and NF are included here for reference.

Swap adjacent cells

This code will swap a cell with it's neighbor to the right. The idea is based off an XOR swap.

In RBF

(>+<)>(<+>)<(>+<)

In NF

*{}*{*{}**{}{}}*{}**{}*{{}*}{*{}**{}{}}

Computation class

Nanofuck is Turing complete, as it is a minimalized version of Reversible Boolfuck, which has been proved Turing complete.

See also

• Reversible Bitfuck
• Picofuck is a project to discover 2 command variants of RBF.
• Boolfuck is Brainfuck on single bit cells.
• BitChanger is a minimal Boolfuck variant.
• Reversible Brainfuck uses the converse of the looping construct used here.
• Smallfuck is another Boolfuck variant.
• Simple translation