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

Computational class

A variant of Cyclic tag which halts when the last production is produced from (rather than when the queue becomes empty) can be easily compiled to Bitdeque as follows:

• Program start: initial string, with each 0 encoded as PUSH and each 1 encoded as INVERT PUSH INVERT.
• Productions, with each production encoded as:
  • EJECT INVERT, then
  • GOTO to the first command of the next production (or the first command of the first production, if this is the last production), then
  • the production itself, with each 0 encoded as PUSH and each 1 encoded as INVERT PUSH INVERT.

This construction works by using the Bitdeque deque as the cyclic tag queue, ensuring that the register is 0 throughout the body of productions (skipping them if the register is 1). If a production is not produced from, it jumps to the next production in cyclic order; if a production is produced from, it falls through into the next production (thus causing the program to end if the last production is produced from).

Cyclic tag is Turing complete even when using this alternative halt condition (the compiled program naturally ends up with this halt condition when compiling a tag system with an explicit halt symbol into cyclic tag), proving that Bitdeque is also Turing complete.

Implementation

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