StackBit

StackBit is a Turing-complete esolang by User:ChuckEsoteric08 that is easy to implement.

Specification

Data is stored in two stacks.

0 - push 0 to the current stack
1 - push 1 to the current stack
~ - switch to another stack
[...] - while top of the stack is 1
* - pop top element

There is also optional command for debuging:

. - outputs top of the stack

Reversible StackBit

In this variation while loop [...] is replaced with a loop similar to Reversible Brainfuck. It has nothing to do with reversibility and word "Reversible" is simply borrowed from it.

[ - if top of the stack is nonzero jump past matching ]
] - if top of the stack is nonzero jump past matching [

StackBit minimalisation

It has 4 characters: >1()

• * is merged with the loop as [*..]*, becoming (...)
• ~0 likewise is merged into >
• It can be shown as equivalent:

StackBit Minimalization
-------- --------------
   ~          >()
   0          >()>
   1          1
   *          (1)
   [          (1
   ]          )>()>

Turing-completeness Proof

The Turing-completeness can be proven by simulating BitBrain-R

Start of the program: 0~000000000~
+ - ~0~
> - ~0~[*~*1~0]*
< - 0~[*~*1~0]*
[...] is same
* - ~1~[~*0~*0]~[*0~*1~]*~

Similar thing applies to Reversible variant, which can simulate Reversible Bitbrain-R in which [ jumps if nonzero, with * implemented like that:

* - ~0~[~*1~*10]~[~*00~]*~*

Examples

Repetition

The following program pushes five one-bits onto the first stack and repeatedly prints and removes the same until the zero-bit on the bottom has been reached. The first version requires the standard StackBit facilities, while the second variation depends on the minimised form.

011111[.*]

Stack Switching

This program pushes five one-bits onto the first stack, repeatedly switches to the second for pushing an equinumerant account of zero-bits onto the second stack, and finally prints while removing the second collection's contents:

011111[*~0~]
~.*.*.*.*.*

Interpreter

• Common Lisp implementation of the StackBit programming language.