BF-SC

From Esolang
Jump to: navigation, search

BF-SC is a language designed by ihope127 to be more powerful than BF-PDA yet less so than Brainfuck. The memory consists of a tape extending to the right only. Every cell has a number: the leftmost is 1, then 2, then 3, etc. Each cell is either "set" or "unset"; all cells start out unset. The "head" starts on cell 1. The instructions:

> Moves the head to the right.
< Moves the head to the left, if possible.
. Outputs the state of the cell under the head.
[ While the cell under the head is unset, set it and...
] End while.

Note that there is no way to unset a cell.

Setting a cell x has the side effect of setting all cells which are x cells to the right of a set cell: for example, setting 3 also sets 6, 9, 12, etc. If 5 is then set, so is 8 (because it's 5 to the right of 3), 11 (5 to the right of 6), 13 (to the right of 8), and, in fact, every cell to the right of those, as they can all be reached as a sum of 3's and 5's.

Not Turing-complete

Every BF-SC program must halt eventually, as such a program is forced to play a game of Sylver coinage against itself (Sylver coinage is known to always "halt").

Possibly, more power may be gained by adding an instruction @ that sets the current cell, and making the while loop not do so.

Even then, all infinite loops are detectable, because such a loop cannot involve setting any cells, as this cannot be done infinitely; a loop must "stall" forever, simply moving right some number of times each time it is executed.

Detecting infinite loops for any given input is impossible for a universal Turing machine. This implies Turing-incompleteness since not every Turing machine can be implemented in BF-SC.