BF instruction minimalization
From Esolang
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: ><+-[].,
Contents |
[edit] 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 -- --- > >>>>>>>>> < <<<<<<<<< + >>>>>>>>[<]@>[@>]<<<<<<<<<[@] - @>>>>>>>>@[<@]>[>]<<<<<<<<<[@] [ @[>>>>>>>>@[<@]>[>]<<<<<<<<<[@]>>>>>>>>[<]@>[@>]<<<<<<<<<@[@ ] >>>>>>>>>@<<<<<<<<<]>>>>>>>>>[<<<<<<<<<@>>>>>>>>>@]<<<<<<<<<] . >.< , >,<
[edit] 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 -- ---------- > }<}}<}}<}}<}}<}}<}}<}}<}}<} < <<<<<<<<< + }<}}<}}<}}<}}<}}<}}<}}<}[<]<}}<}[<}}<}]<<<<<<<<<[<}] - <}}<}}<}}<}}<}}<}}<}}<}}[<<}]}<}[}<}]<<<<<<<<<[<}] [ <}[}<}}<}}<}}<}}<}}<}}<}}<}<}[<<}]}<}[}<}]<<<<<<<<<[<}]}<}}<}}<}}<}}<}}<}}<}}<}[<]<}}<}[<}}<}]<<<<<<<<<<}[<} ] }<}}<}}<}}<}}<}}<}}<}}<}}<}<}<<<<<<<<<]}<}}<}}<}}<}}<}}<}}<}}<}}<}[<<<<<<<<<<}}<}}<}}<}}<}}<}}<}}<}}<}}<}<}]<<<<<<<<<] . }<}.< , }<},<
[edit] 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:
} >@ < < [ [ ] ] ; [.<]<[,<]
[edit] 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
[edit] 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.
[edit] Notes
[edit] On Jix's I/O
With the code "; = [.<]<[,<]" in the 5-instruction set by jix you can never output value 0, cause it will skip the loop. The following can:
? Core -------------- ; [<,>]@[<.>@] BoolFuck ? -------------- . }[<}]; , }[<}]<};
[edit] 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.
[edit] 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.
