Programming in 1L a/Flattened 1L a
A way to create 1L_a programs is to write the corresponding Brainf*** program first, and then convert it into 1L_a. So it's time for a new language, Flattened 1L_a, which took place between 1L_a and Brainf***.
Brainf*** and its minimalizations
As you might know, Brainf*** is a well-known and one-dimensional programming language. Like 1L_a, there's DP and IP too, yet the DP only moves in a line, and the DP moves on a character array instead of a bit array. It is Turing complete and has 8 instructions. Here are them:
|>||Move the DP to the right|
|<||Move the DP to the left|
|+||Increment the memory cell the DP is pointing at|
|-||Decrement the memory cell the DP is pointing at|
|.||Output the character pointed by DP|
|,||Input a character and store it in the cell at the DP|
|[||Jump past the matching ] if the cell at the DP is 0|
|]||Jump back to the matching [ if the cell at the DP is 0|
Yet, as a Turing-Tarpit(languages that are designed to be both have only a few instructions and is Turing-Complete), 8 instructions are a bit too much. So we may create Brainf*** equivalents that have less instructions.
We call a language Brainf*** equivalent if you can implement every instructions in the language in Brainf*** and implement every instructions in Brainf*** in the language.
It's pretty much obvious that we can reduce Brainf*** to 7 instructions by operating on an array of bits(like 1L_a!) instead of an array of characters, so that the instruction + and - become one: the toggle operation, notated as @. It is possible to use our powerful flow control to simulate a character array, but it would be bulky and I'm too lazy to do that. Luckly, someone have already done it for us:
Brainf*** The new language --------- ---------------- > >>>>>>>>> < <<<<<<<<< + >>>>>>>>[<]@>[@>]<<<<<<<<<[@] - @>>>>>>>>@[<@]>[>]<<<<<<<<<[@] [ @[>>>>>>>>@[<@]>[>]<<<<<<<<<[@]>>>>>>>>[<]@>[@>]<<<<<<<<<@[@ ] >>>>>>>>>@<<<<<<<<<]>>>>>>>>>[<<<<<<<<<@>>>>>>>>>@]<<<<<<<<<] . >.< , >,<
We call this language Boolf***. Since Brainf*** is Turing-Complete, and you can translate any Brainf*** program into Boolf*** program, Boolf*** is Turing-Complete too.