Talk:BF instruction minimalization
From Esolang
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)
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 ~~~~)
