Brainfuck derivatives with nontrivial computational class proofs

From Esolang
Jump to navigation Jump to search

This is a list of, as the name implies, brainfuck derivatives with nontrivial computational class proofs. It is for compiling brainfuck derivatives deemed "objectively interesting" by #esoteric by the standard of nontrivial computational class proofs. The plan was originally just interesting ones, but it was felt that that would not be objective enough, and that trivial languages like Ook! would eventually be added, thus degrading the page's integrity.

This page is meant to compile not links, but full passages, so long as the description is short enough, such as to minimize the number of new pages.

Note that strict supersets of Brainfuck, along with Trivial Brainfuck Substitutions, are not applicable by nature.

Permanent Brainfuck

The first BFDWaNTCCP is "Permanent Brainfuck", named by ais523 on #esoteric. Permanent Brainfuck is a brainfuck without a - (decrement) instruction, but that still has unbounded cells. This makes it so that, once a cell is incremented, it can never be zero again.

It should be noted that unbounded cells are important: each cell starts at 0 and can be successively incremented to any natural number, but never decremented. A bounded-cell implementation is trivially turing complete, because "-" can be replaced with "+" repeated wrappoint-1 times. Unbounded cells, on the other hand, being infinite, are undecrementable.

The most promising method for proving its computational class is Minsky machines.

See Brainfuck minus -, which shows that ordinary brainfuck without '-' and no cell-wrapping is Turing-complete, and therefore shows that Permanent Brainfuck is Turing-complete too.