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)

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.


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 +

Iamcalledbob's attempt

This attempt starts the pointer at #1. The pointer cannot reach #0.

><@.,[]       change + and - into @, or change the bit(also change the #0 value)
><@[]         stdio is unnecessary.
><@|          |= [ or ]  like this: || = []
:<|           combined > and @
:|            : = < if the bit pointed is 1
|             | = : when #0 = 1

This attempt starts the pointer at #1. The pointer cannot reach #0.

><+-.,[]
|             | determines on input--- all the instructions above

Stuck? We'll try again

All of this is written by User:A.

We'll start with :

+-<>[],.

Step 1 (Overflow Control) (CMD = 7)

+<>[],.

we don't need the -. When + makes the pointer byte be 255, set the pointer byte to 0.

Step 2 (Array I/O)(CMD = 5)

+<>[]

set Cell #1 to the out cell, Cell #0 to the in cell. When it is toggled(set all the way from 0 to 255), it will perform input/output on cell #2.

Step 3 (Combine < and +) (CMD = 4)

<>[]

The < becomes the original <+.

Step 4 (Jump command) (CMD = 3)

<>|

The | is the jump symbol. It would make the pointer jump forward n+1 (n=the cell byte value) commands. This still makes a loop available.

Aha!

I found that I can also put the loop on the array.

Step 5 (Putting loop on array) (CMD = 2)

<>

Only 2 commands left! Let me explain that:

I put the loop toggle on cell #3.
If it is put into a value, and the cell #4 is toggled, it will make the code jump n+1(n=the value on cell #3) commands forward.

Yay! I found a 2-command possibility.

Step 6 (Aha! Using current cell) (CMD = 1)

Thanks! AshuraTheHedgehog! You gave me an inspiration!

>

Haha! 1 instruction! Let me explain that. Like what AshuraTheHedgehog said, > = < if the cell is odd. That means, when the byte under the pointer is odd, the > command will be the < command.

That means that Brainf*ck can be simplified into only 1 instruction!!

Good news

I just found that the 3-byte Brainfuck is Turing-complete!!! See here:Collatz function

This attempt is written by User:A.

Step 1

Starting with...

+-,.<>[]

Since 3-bytes keeps it Turing-complete, it can be:

+->,.[]

Tada!!

Step 2

+->,.|

Combined [ and ], of course.

Step 3

Memory mapping. Just can't stop this step.

+->|

Step 5

Mapped loop again.

+->