brainflop
brainflop is a Turing tarpit by user:InfiniteDonuts. It is Turing-complete, minimalist, and inspired by HighFive. It has 7 instructions that manipulate an array of 1024 memory cells. It is also quite possibly the most horrible language ever invented, as it not only extremely minimalist but causes insanity if used for too long. The author of this language tried to make a truth-machine program unsuccessfully and nearly lost his mind.
Commands
brainflop has 7 commands, down from brainf***'s 8, and it is still Turing complete (although it would be a nightmare to program in it):
+ increment the memory cell under the pointer - decrement the memory cell under the pointer < move the memory pointer left > move the memory pointer right * If the memory cell is 0, get input. Else, print the cell's corresponding ASCII character. / If the cell is 0, skip the next command. Move the program pointer the number of spaces indicated by the cell to the right of the memory pointer (negative goes backwards, positive goes forwards). # Set the current cell to 0.
Example Programs
Hello World
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++* +++++++++++++++++++++++++++++* +++++++** +++*# ++++++++++++++++++++++++++++++++* +++++++++++++++++++++++++++++++++++++++++++++++++++++++* ++++++++++++++++++++++++* +++* ------* --------*
Cat
>----<#**/
Truth-machine
>++++>+++++++++++++++++++++++++++++++++++++++++++++++++>-- <<<*------------------------------------------------/o>/>> <*/____These chars are skipped_________________-*
Other example programs
Other simple programs have been attempted, but most are sadly impossible due to brainflop's tendency to cause its programmers to lose their minds.
Computational class
(Note: the specification above is ambiguous, and the link to the interpreter is dead so that can't be used to clarify it. This proof assumes that either the / command either does not move the program pointer if the cell the data pointer is pointing to is 0, or moves it one step forward regardless of the value of the cell to the right – these behaviours can be made equivalent by adding a comment.)
Assuming each cell can store unboundedly large integers, brainflop is Turing-complete because it can directly implement The Waterfall Model on up to 512 counters (far more than are required for Turing-completeness), with the program arranged so that there is exactly one halt counter, which comes last in the list of counters. Such an implementation can start by unconditionally (and without control flow) initialising the tape to alternate between waterclock values and jump distances (each / command in the generated program always runs with the data pointer in the same place and always jumps to the same place, and no two different / commands are run with the same data pointer, so the jump distances can be hardcoded), then moving the data pointer to the halt waterclock. The program then consists of direct implementations of the zeroing triggers for each of the counters from left to right; before the code for each of the zeroing triggers, code is added to move the data pointer to the cell implementing the corresponding waterclock, followed by a / command that will jump over the zeroing trigger if the waterclock is not actually zero. The halt waterclock does not have a zeroing trigger; rather, it is preceded by code that performs the steady decrement, and a / command on the halt waterclock is used to jump back to the end of initialization (when the data pointer was over the halt waterclock) – the start of the non-initialization code will then move the data pointer back to the first waterclock, check its zeroing trigger, etc., and thus the program ends up forming one big loop that implements The Waterfall Model.
Due to the bounded length of the tape, brainflop cannot be Turing-complete if the cells are bounded because then it would not be able to access arbitrary amounts of memory.