Bueue

Bueue (pronounced Büü) is an esoteric programming language. Every integer greater than 0 is a valid Bueue program. The integer is expanded to its Collatz sequence, which is then interpreted as a collection of sub-programs. Data is stored on a bit queue. The queue is shared between sub-programs. It is unknown if there are finite numbers that generate infinitely large Bueue programs.

Instructions

Instr. Description
0 Enqueue 0.
1 Enqueue 1.
2 Jump marker.
3 If the bit at the front of the queue is not 0, jump back to the last jump marker.
4 If the bit at the end of the queue is not 0, jump back to the last jump marker.
5 Rotate the queue (towards the front).
6 Flip the bit at the front of the queue.
7 Dequeue the bit at the front of the queue (that is, drop/remove it).
8 Print bit at the front of the queue.
9 Dequeue 8 bits (1 byte); convert to char (ascii) and print.

Implementation

(Python)

```import sys

# Just to ensure that it really is a long.
num = long(raw_input())

# Programs are collatz sequences
def collatz(n):
while n != 1:
yield n
if n > 1:
if n % 2 == 0:
n = n / 2
else:
n *= 3
n += 1
yield 1

bueue = []

# Language specification
#  A bueue program is a simple number
#  The bueue interpreter generates the collatz sequence
#  of that number and interprets each number in it as
#  a small subprogramm.
#
#  There is a queue available which can store bits.
#  Opcodes:
#   0 - enque 0
#   1 - enque 1
#   2 - jump marker
#   3 - if bit at front of the queue is not 0
#       jump back to the last jump marker
#   4 - if bit at end of the queue is not 0
#       jump back to the last jump marker
#   5 - rotate queue (rotate left)
#   6 - flip bit at the front of the queue
#   7 - deque bit at the front (that is
#       drop/remove it)
#   8 - print bit
#   9 - deque 8 bits (1 byte) convert to char (ascii) and print

for i in collatz(num):
prg = str(i)
#print "Debug: ", prg
#raw_input()
pos = 0
max_pos = len(prg)
poss = []
while pos < max_pos:
#print " ",bueue
c = prg[pos]
if(c == "0"):
bueue.append(0)
elif(c == "1"):
bueue.append(1)
elif(c == "2"):
poss.append(pos)
elif(c == "3"):
if(len(poss) < 1):
break
if(len(bueue) < 1):
break
if(bueue != 0):
pos = poss.pop()
continue
elif(c == "4"):
if(len(poss) < 1):
break
if(len(bueue) < 1):
break
if(bueue[-1] != 0):
pos = poss.pop()
continue
elif(c == "5"):
if(len(bueue) < 1):
pos += 1
continue
bueue = bueue[1:] + [bueue]
elif(c == "6"):
if(len(bueue) < 1):
pos += 1
continue
if(bueue == 0):
bueue = 1
else:
bueue = 0
elif(c == "7"):
bueue = bueue[1:]
elif(c == "8"):
if(len(bueue) < 1):
pos += 1
continue
sys.stdout.write(str(bueue))
elif(c == "9"):
if(len(bueue) < 8):
pos += 1
continue
bits = bueue[:8]
bueue = bueue[8:]
bits = reduce(lambda a,b: a + b,map(str,bits))
ch = chr(int(bits,2))
sys.stdout.write(ch)
pos += 1

```

Example programs

So far not many example programs are known. It is known that `5` prints 0 and `13` prints 1. One can find more or less easily example programs by writing a program and ensuring that the interpreter stops at the last few digits so it does not evaluate other sub-programs by computing the Collatz sequence of your program. (Although that would only be possible if the interpreter had a bug which made it stop ;)). If you don't care to what the sub-programs evaluate (i.e if you don't even care if your program does not terminate) then finding example programs is trivial.

```11000011694
```

With some imagination prints 'Cool' although it really prints 'COO1' and then loops forever.

```1100100069011001019011011009011011009011011119
```

Prints 'Hello' and then does something else.

Truth-machine

```x009
```

(x being either 1 or 0).

Computational Class

A single sub-program is probably not Turing complete, as the looping instructions are very restricted.

It's currently unknown whether a finite set of sub-programs is Turing complete (if the corresponding Collatz sequence reaches 1 and halts).

Since it is unknown whether the corresponding Collatz sequences reach 1 for all numbers or enter an infinite cycle, a Bueue program could produce an infinite number of sub-programs, which leads to the question whether an infinite amount of each non-Turing complete sub-program can yield Turing completeness.

However, everything is unknown. Because there is no proof (yet) whether a Collatz sequence of a given number reaches 1 or not, it is generally undecidable (for now) whether a Bueue program terminates.