Talk:BF instruction minimalization
I've been thinking about a 2-instruction BF where the two instructions would be for example b and f, and with the following translation table of Brainfuck commands to this 2-instruction version: >: bbb, <: bbf, +: bfb, -: bff, [: fbb, ]: fbf, .: ffb, ,: fff. So I got the two instructions and the translation table ready, now all that's left is finding a description of the "b" and the "f" instruction that makes it seem as if those are two complex instructions, and the result of this description will be that the combinations I gave in the translation table will really have the correct Brainfuck effect.--Aardwolf 22:09, 8 Sep 2005 (GMT)
- Hmm... sounds like cheating to me >:-) but if you can figure out a way for it to work... go ahead. --Ihope127 17:37, 9 Sep 2005 (GMT)
- Uh, no, I think it's impossible: [ and ] both modify the bracket count, while nothing else does. There's no way for an instruction to "sometimes" modify the bracket count. --Ihope127 19:33, 27 Sep 2005 (GMT)
- Concept has already been done. --Thematrixeatsyou 05:29, 16 Jul 2006 (UTC)
- He's saying something different. b and f would in that case be two well-defined functions, not bits that encode other operations with a huffmanish code. Ihope27's argument does not exactly hold up either. It is certainly possible for an instruction to "sometimes" modify the bracket count. For instance, if the "real" bracket count was floor(bc), and "b" incremented bc by 0.1 while "f" decremented it by 0.1. Then, "b" would only modify the "real" bracket count if the number of b's in a string exceeded the number of f's in that string by ten or vice versa. As a matter of fact, the original "[" only sometimes modifies the bracket count--precisely when the data under the read head is nonzero.--Quintopia 06:50, 2 October 2008 (UTC)
Couldn't this:
} = >>@ ( = [<@> ) = @]<[>@<@]< . = . , = ,
...be simplified to this?
} = >>@ O = [<@>@]<[>@<@]< . = . , = ,
And then could the User:jix solution be used as well? --Ihope127 22:10, 16 Sep 2005 (GMT)
- Uhm. I don't see how the looping would work. --BodyTag 08:26, 17 Sep 2005 (GMT)
- ...Heh. :-) But still, couldn't you combine the jix solution with the () one? --Ihope127 21:56, 17 Sep 2005 (GMT)
You know, I/O could be eliminated altogether, and then maybe "^" could be redefined as what is now "}^"? It, heh, might work.
- About your I/O Elimination, Ihope127... You can't do it. Sure you can, but the result wouldn't be brainfuck-complete. Brainfuck DOES have I/O. --BodyTag 15:10, 8 Oct 2005 (GMT)
- Hmm, well, there probably would be I/O, but just not I/O instructions. --Ihope127 15:53, 9 Oct 2005 (GMT)
Heh, more ramblings. The optimal Brainfuck probably contains only two instructions, which are "brackets" of some sort. *Something* must modify bracket count, and thus you might as well eliminate everything *but* that which modifies bracket count. (And I don't like the ^ instruction, as it pretty much removes half of what makes Brainfuck what it is. And can it really be expressed as a complex instruction?) --Ihope127 15:53, 9 Oct 2005 (GMT)
You can see how to eliminate instructions ,but you should also see how it can be compressed. Normal brainfuck is 3-bits per instructions, with 4 instructions they are 2-bits per instructions. But how long would a program be when converted from 3-bi instructions to 2-bit instructions? --Zzo38 (unsigned)
- Normal BF doesn't have to have 3 bits per instruction; as long as you're not in a loop, you can cut a bit off one of the instructions, because it doesn't have to be distinguished from ].
- If you aren't in a loop, you don't use a ] command, and some commands you don't use them in certain sequences ({=beginning of file, }=end of file): {] [} [] +- -+ <> >< ][ -} +} <} >} and some sequences are equivalent: [+]/[-] [[x]]/[x] [>]<[>]/[>] (where x is anything) --Zzo38 17:53, 16 Jun 2006 (UTC)
I don't see why you need to convert to bit-arrays. Here is a 5-instruction version of my own invention which will work in 8-bit (and larger sizes) BF:
The current cell is denoted (x). The value in the parentheses can also be any value, it denotes the corresponding memory cell.
+ Adds 1 to (x), if cell reaches numerical limit (like 255 in 8-bit BF), overflow back to 0 < Works as in BF > Works as in BF . IF (x+1) = 0, output; ELSE input ^ IF (x+1) = 0, do nothing; ELSE go back (x)+2 *** instrctions before the current instruction
*** (x)+2 because this is equal to skipping (x) instructions in the middle.
I can't find a translation table yet, but I guess this is Turing-complete too. This is a cat program I wrote in my free time, the input string is null-terminated. Comments don't count as instructions and do not affect the behaviour of "^":
leave a zero cell to mark start of string
>
loop #1 input string
>>>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++<.<++++++>>
^ bootstrap to traverse loop larger than 256 instructions
>><< junk instructions to keep both halves exactly 142 instructions long
<<++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++^
loop #2 loop back to start of string
<++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+++++++++++++++++++++++++++++++++++
>>>>>><<<<<< more junk
<<^
loop #3 to output
>>>>.<
<+> to change parity of instruction count, this has a side effect of adding 1 but it doesn't
matter because we won't we working on that memory anymore
more junk instructions
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<^
'.' and ',' seem poorly defined, they appear to input/output whole bytes in a languages that operate on bit. --(this comment by 67.114.109.71 at 02:56, 9 Sep 2006 UTC; please sign your comments with ~~~~)
Would it be ill-advised to replace [ and ] with a branch instruction ^ that, if the current bit is 1, reads the next 16 bits as a number n and goes to the nth occurrence of ^? In other words, it combines "label" with "branch if nonzero (bnz)." Obviously it then imposes an upper limit of 65k loops, but when you compile it to assembly, you get such a limitation anyway. --Quintopia 18:49, 25 September 2008 (UTC)
- That wouldn't sacrifice Turing-completeness; you could easily write a brainfuck interpreter in brainfuck without exceeding that number of loops, and use ++++++++>++++++++++++>++++++++++++++> and so on to store an initial program into memory. The result would be a lot slower than a program that hadn't been modified that way, though. --ais523 19:13, 25 September 2008 (UTC)
- It would also be rather un-BFey, I suppose, since the "spirit" of BF is that no operation takes a numerical argument. (Only [ takes an argument, and that in the form of the boolean result of a test.)--Quintopia 06:36, 2 October 2008 (UTC)
- That sounds like Vrejvax's jnz instruction. It's possible to work around the 65k restriction by, if the 16 bits are all zero, reading the next 16 bits and adding 65536 to that, and if those are all zero, adding 65536 and reading in the next 16 bits, and so on. Not that anyone would ever need more than 65k loops, however... --Nortaneous 04:07, 8 November 2008 (UTC)
Inverse instruction?
Here's my method.
Old|New + |+ - |+I < |< > |<I . |. , |.I [ |[ ] |[I
Therefore:
+<.[I This way, we only have 5 instructions, instead of 8.
--Alegend 00:23, 11 August 2009 (UTC)
I don't quite see. If the I is part of the instruction, then > and >I would be two different instructions. Orange 03:42, 11 August 2009 (UTC)
According to the way above, I isn't really its own instruction but instead is a suffix (a prefix might do better). If I was made its own instruction, you would instead get:
Old|New + | + - |I+I < | < > |I<I . | . , |I.I [ | [ ] | ]
--Zzo38 18:09, 11 August 2009 (UTC)
But I>I and > are still two different instructions, even if they use the same ascii character with a suffix they still do two different functions. Orange 18:54, 11 August 2009 (UTC)
- That might be it if the I instruction selected between two instruction sets (which is not what we wanted, though), but it can be done differently, too. Maybe what I really does is it flips the entire tape around, that way I>I is just three instructions. If the cells are bits then you don't need + and - separately. But that doesn't apply for I/O, obviously, so for I/O you would need to make it differently --Zzo38 00:47, 9 January 2010 (UTC)
Oh, sorry! But, we still have a good minimalization, here, huh? --Alegend 00:40, 12 August 2009 (UTC)
Back to your question. Just note that I may flip + into -, < into>, . into , ,and [ into ]. Actually, that may work. And, as User:Zzo38 said, + and - can be combined.----User:A 13 Jul. 2018
How about this?
This is what I thought:
< = <^; ! = }^;^
Wouldn't this be okay? Or can't I use the jix's I/O, or the skip next if zero? --Wh1teWolf 21:31, 11 December 2009 (UTC)
Input/Output
You don't need instructions for I/O. You could take all input in the beginning with an unstated .[>.] and write all output at the end, with an unstated {,<} (where {} loops until it reaches the first cell).
You loose interactive input, but who cares ? Any brainfuck program can be written with all input at the beginning.
You loose on-the-fly output. That might be a problem : a program with an infinite loop will output nothing. You can fix this by asking the user an upper bound, and stopping the execution after this number of iterations. You could also decide that using < while on the first cell will not cause a crash but rather output the content of cell N, where N is the content of cell 1.
Using {>[] (where { is <+) you get a 4-instructions BF-complete language. I don't think we can call BF-complete any language with ^ instead of [] --(this comment by 89.2.114.165 at 21:30, 7 May 2010 UTC; please sign your comments with ~~~~)
- Well the article does say "I/O is a requirement for BF-completeness". Without I/O you are essentially minimizing P′′ instead. In fact the only difference from P′′ in your suggestion is that P′′'s λ is +< rather than <+. --Ørjan 23:13, 7 May 2010 (UTC)
- I'm not talking about suppressing I/O ; what I meant is that I/O could be done automatically, at the beginning and at the end, without having instructions for it 89.2.114.165 13:48, 9 May 2010 (UTC)
And, is memory mapping okay? (That will never be minimizing P’’.) ----User:A13 Jul. 2018
Input determination
Can I merge all the instructions into 1 command? Like:
|
This command changes into the input and is executed as in Brainfuck.
- The resulting language would be ℒ-complete, not Turing-complete. (See also Easy, which is a more fleshed-out version of this idea.) That's normally considered to be something quite different from a minimalization, though. --ais523 13:00, 13 July 2018 (UTC)
Opcodes
Apparrently, reducing to only 2 commands is technically not possible as input and output will already take 2 options. This can be avoided by adding opcodes, maybe 0 for input and 1 for output. In that case we can define it this way that, If m[] is 0, then . operation will take a single character input to m[+1] and if m[] is 1, then it will output the ascii of m[+1] to the console. We can do the same for > and < maybe but that will introduce further complications only and eventually introduce a new language apart from brainfuck itself.
Now if we have to define a new language, we can use a memory tape and an opcode counter to create some brainfuck code and when EOF arrives, we can execute the BF code. So maybe ! will execute the opcode and + will be used to increase the opcode counter by 1. We can limit the opcodes from 0 to 7 as there are only 8 bf commands and when opcode counter is 7, + will take it back to 0.
Basically, when the program starts, a = 0, m = ""
x = {".", ",", "+", "-", ">", "<", "[", "]"}
+ -> a = (a + 1) % 8
! -> m += x[a]
And when we find EOF, we can execute m as a brainfuck code.
-- Pptx704 (talk) 17:44, 22 March 2022 (UTC)
6-Instruction Bitchanger
As of 07:58, 23 June 2022 (UTC), is the 6-instruction Bitchanger shown on the page the smallest universally accepted BF instruction minimalisation? I am asking this because I have an idea for a 2D minimal BF, but I want to use the smallest universally accepted one, not necessarily the smallest one. Squidmanescape (talk)
1 bit bf to my bf instruction minimalization
1bit bf|my try
¬|> <<
>|> << >
<|<<
(|<><
)|<>>