# BF instruction minimalization

Our goal is to reduce the number of BF instructions as far as possible (without regard to symmetric style), but not using tricks such as cycling through instructions with one instruction and executing them with the other. The idea is that the symbols representing the instructions are well defined and the functions they represent do not change during runtime. I/O is a requirement for BF-completeness. We start with the standard BF instructions:

```8 instructions: ><+-[].,
```

## Formalizing requirements

Our goal of reducing the number of BF instructions without using tricks may require some formalism. Consider some language X. For the purposes of this page, we will call X BF-equivalent if there exists a simple mapping from X to BF and from BF to X. By simple mapping we mean that each command in X can be substituted by a finite number commands in BF which perform the same function. Conversely, each command in BF may also be substituted by a finite number of commands in X which perform the same function. Consider replacing "+" and ">" with "}". The simple mapping from X to BF would be

```X  BF
-- ---
}  +>
<  <
-  -
[  [
]  ]
.  .
,  ,
```

The simple mapping from BF to X would be

```BF X
-- -
>  -}
<  <
+  }<
-  -
[  [
]  ]
.  .
,  ,
```

Thus X is BF-equivalent. Notice that these substitution must be context-free. Braincrash and other Turning tarpits do not meet this requirement because there is not a single sequence of BF commands which may be substituted for "!" that performs the same function (it is context dependent). Unary and other encoding schemes are excluded for the same reason. Someone correct me if I've made any mistakes -- User:Orby

### Further formalizing requirements

Another way of asking, "What is the smallest brainfuck derivative?" is to ask, "What is the rank of the brainfuck monoid?". Brainfuck is a concatenative language. Concatenative languages are monoids. Monoids have a rank (e.g. the cardinality of the smallest generating set). Clearly rank(bf) > 1, otherwise bf would be commutative.

## Boolfuck (7 instructions)

BF is normally 8 or more bits wide. Let's just use one bit (and assume an 8-bit BF), that gives us a new intermediate language (similar to Boolfuck):

```7 instructions: ><@[].,
```

The new instruction "@" flips the bit (this takes care of the previous "+" and "-" at once). Here is a conversion chart:

```BF bit
-- ---
>  >>>>>>>>>
<  <<<<<<<<<
+  >>>>>>>>[<]@>[@>]<<<<<<<<<[@]
-  @>>>>>>>>@[<@]>[>]<<<<<<<<<[@]
[  @[>>>>>>>>@[<@]>[>]<<<<<<<<<[@]>>>>>>>>[<]@>[@>]<<<<<<<<<@[@
]  >>>>>>>>>@<<<<<<<<<]>>>>>>>>>[<<<<<<<<<@>>>>>>>>>@]<<<<<<<<<]
.  >.<
,  >,<
```

### BitChanger (6 instructions)

Next, it can be observed that the sequence ">@ < >@" performs the same function as ">" (see BitChanger):

```6 instructions: }<[].,
```

The new instruction "}" is defined in terms of the previous ">@".

```BF BitChanger
-- ----------
>  }<}}<}}<}}<}}<}}<}}<}}<}}<}
<  <<<<<<<<<
+  }<}}<}}<}}<}}<}}<}}<}}<}[<]<}}<}[<}}<}]<<<<<<<<<[<}]
-  <}}<}}<}}<}}<}}<}}<}}<}}[<<}]}<}[}<}]<<<<<<<<<[<}]
[  <}[}<}}<}}<}}<}}<}}<}}<}}<}<}[<<}]}<}[}<}]<<<<<<<<<[<}]}<}}<}}<}}<}}<}}<}}<}}<}[<]<}}<}[<}}<}]<<<<<<<<<<}[<}
]  }<}}<}}<}}<}}<}}<}}<}}<}}<}<}<<<<<<<<<]}<}}<}}<}}<}}<}}<}}<}}<}}<}[<<<<<<<<<<}}<}}<}}<}}<}}<}}<}}<}}<}}<}<}]<<<<<<<<<]
.  }<}.<
,  }<},<
```

### Combined I/O expansion (5 instructions)

```5 instructions: }<[];
```
```; = [.<]<[,<]
```

A five instruction solution, by User:jix can be formed by combining input and output. Simplified by User:calamari:

```intermediate  jix
------------  ---
}             }
<             <
[             [
]             ]
.             [<}]}<}[<}]}<}[<}]<};
,             [<}]}<}[<}]<}}<}[<}];
```

We now have five instructions:

```} >@
< <
[ [
] ]
; [.<]<[,<]
```

### Skip If Zero expansion (4 instructions)

```4 instructions: < } ^ ;
```

Four instruction possibility, by User:calamari. The program is contained in the unstated loop, +[ instructions ]:

```instruction  meaning
-----------  -------
<            <
}            }
^            skips the next instruction if the byte at the pointer is 0
;            ; by jix
```

It's not immediately clear how to achieve loops of specified sections of code with this architecture (although it may be possible).

--Quintopia 23:34, 24 September 2008 (UTC)

Store the id of the loop and conditionally execute it's contents. ^ should be skip until next ^ if 0 at pointer and no-op for every second ^. I'm assuming that ^ works this way below. Example:

```--<-<<+[+[<+>--->->->-<<<]>]<<--.<++++++.<<-..<<.<+.>>.>>.<<<.+++.>>.>>-.<<<+.
```

Can be divided into multiple parts and given each part an id

```1 --<-<<+[
2 +[
3 <+>--->->->-<<<]
4 >]
5 <<--.<++++++.<<-..<<.<+.>>.>>.<<<.+++.>>.>>-.<<<+.
```

On the tape, every second cell is used for data, others are for the loop id. We do some command conversion

```+ to >+< to -}}<< to }< 255 times and }}<<
- to >-< to -}-< to }< 255 times and } and }< 255 times and }<<
[ to >^<+>^< to -}^<}^< to }< 255 times and }^<}^<
] to >^<->^< if it contains no nested loops
> to ^}-}}<<<^ 255 times
< to ^}<<<}-}^ 255 times
insert +, so }< after the end of each part and ^}<^ 255 times after last part
```

The only problem with this is that ^ can't be nested, therefore this approach is impossible. ^ must have a pair that's different from it to make this work. Another way would be that ^ skips 2 commands instead of 1 and if one of them is a ^, it also skips that ^'s skipped commands, so ^^^}<}< would be entirely skipped if the cell at the pointer is 0. --GDavid (talk) 13:09, 26 August 2018 (UTC)

### I/O goes left (3 instructions)

A three instruction possibility by User:ihope127:

```( >@[
] ]
; [.<]<[,<]
```

This exploits the fact that ; always causes the pointer to move left.