Nanofuck

Nanofuck (NF) is a simple translation of Reversible Bitfuck (RBF) in 3 commands discovered in 2017 by User:Orby. Most people will find it easier to program in RBF as an intermediate language.

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).

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.

Simple translations

There is a simple translation from NF to Reversible Bitfuck given by the following translation table:

NF	RBF equivalent
*	+>
{	<(
}	)

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

The minimal equivalence relation required to make this work for NF is "" ≈ "{}*{}*", as shown in the following table:

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

As a consequence of the reversibility of RBF, there exists a dual simple translation given by the following translation table with minimal equivalence relation "" ≈ "*{}*{}":

NF	RBF equivalent
*	<+
{	(
}	)>

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

See also

• 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.