Bitdeque

Bitdeque is an esoteric programming language created by User:Nobody in 2019. It operates on a deque of bits and a register.

Overview

Bitdeque operates on a deque of bits and a register. When the program starts, the deque is empty and the value in the register is 0. There is (currently) no I/O.

Instructions

Bitdeque has 6 instructions:

• PUSH: Push the bit in the register to the right side of the deque (Does not change the bit in the register)
• INJECT: Push the bit in the register to the left side of the deque (Does not change the bit in the register)
• EJECT: Pop the bit from the left side of the deque to the register (This removes the bit on the left. The register becomes 0 if the deque is empty)
• POP: Pop the bit from the right side of the deque to the register (This removes the bit on the right. The register becomes 0 if the deque is empty)
• INVERT: Invert the bit in the register
• GOTO: Take a number N (specified in the program) and go to the Nth operation in the program if the bit in the register is 1

Examples

Hello, world!

The following example stores the binary ASCII values of each character in 'Hello, world!' in the deque:

[H] 100 1000: INVERT PUSH INVERT PUSH PUSH INVERT PUSH INVERT PUSH PUSH PUSH
[e] 110 0101: INVERT PUSH PUSH INVERT PUSH PUSH INVERT PUSH INVERT PUSH INVERT PUSH
[l] 110 1100: PUSH PUSH INVERT PUSH INVERT PUSH PUSH INVERT PUSH PUSH
[l] 110 1100: INVERT PUSH PUSH INVERT PUSH INVERT PUSH PUSH INVERT PUSH PUSH
[o] 110 1111: INVERT PUSH PUSH INVERT PUSH INVERT PUSH PUSH PUSH PUSH
[,] 010 1100: INVERT PUSH INVERT PUSH INVERT PUSH INVERT PUSH PUSH INVERT PUSH PUSH
[ ] 010 0000: PUSH INVERT PUSH INVERT PUSH PUSH PUSH PUSH PUSH
[w] 111 0111: INVERT PUSH PUSH PUSH INVERT PUSH INVERT PUSH PUSH PUSH
[o] 110 1111: PUSH PUSH INVERT PUSH INVERT PUSH PUSH PUSH PUSH
[r] 111 0010: PUSH PUSH PUSH INVERT PUSH PUSH INVERT PUSH INVERT PUSH
[l] 110 1100: INVERT PUSH PUSH INVERT PUSH INVERT PUSH PUSH INVERT PUSH PUSH
[d] 110 0100: INVERT PUSH PUSH INVERT PUSH PUSH INVERT PUSH INVERT PUSH PUSH
[!] 010 0001: PUSH INVERT PUSH INVERT PUSH PUSH PUSH PUSH INVERT PUSH

Implementation

• A Python interpreter by User:Bangyen.
• User:Nobody is also currently writing an interpreter for this.

Computational class

According to User:Camto, Bitdeque is Turing-complete, because with a 0 in the middle and 1's on the left and right, one can simulate a Minsky machine with 2 registers, which is Turing-complete.