BF instruction minimalization

From Esolang
Jump to: navigation, search

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

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)

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.


Notes

On Jix's I/O

With the code "; = [.<]<[,<]" in the 5-instruction set by jix you can never output value 0, because it will skip the loop. The following can:

?         Core
--------------
;         [<,>]@[<.>@]

BoolFuck  ?
--------------
.         }[<}];
,         }[<}]<};

But the first loop "[<,>]" looks like an infinite one. We could make it like this: [<,>@]@[<.>@] so that the first loop breaks sometime but then it will be impossible to enter the second loop when appropriate as the value of the bit that selects the I/O operation is lost in the first loop. We could use two bits for selection or copy the bit in the cell next to it. -- (Tritonio) 150.140.227.112 22:50, 6 August 2008 (UTC)

[<[.<]]<[,<] would be able to print a single zero. --Quintopia 22:41, 24 September 2008 (UTC)

Combined <[

You can also combine < with [ (proposed by Aeron), creating <[ = |

?         Core
--------------
|         <[

BoolFuck  ?
--------------
<         |]
[         }|]}|

This creates a 4-source-instruction set with a 7-core-instruction set:

?         Core
--------------
}         >@
|         <[
]         ]
;         [<,>]@[<.>@]

BoolFuck  ?
--------------
@         |]}
<         |]
>         }|]}
[         }|]}|
]         ]
.         }}|]}|<}];
,         }}|]}|<}]<};

This looks inefficient, but it's a possibility.

But hang on...

User:Thematrixeatsyou has spotted a flaw with Aeron's version. If the Brainfuck architecture effectively remains unmodified, and the bit at the pointer equals 1, the program will enter an infinite loop. So it would require an alternative architecture, like the Gregor Richards version of BitChanger.

AshuraTheHedgehog's attempt

><+.,[]	removed -
><+.[]	. = , iff index is odd
>+.[]	> = < iff current cell is odd
>+[]	+ = . iff flag = 1 [uses bits]
>+;	; = [, ], [, ], etc
:;	Combined > and +