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] != 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[0]]
    elif(c == "6"):
      if(len(bueue) < 1):
        pos += 1
        continue
      if(bueue[0] == 0):
        bueue[0] = 1
      else:
        bueue[0] = 0
    elif(c == "7"):
      bueue = bueue[1:]
    elif(c == "8"):
      if(len(bueue) < 1):
        pos += 1
        continue
      sys.stdout.write(str(bueue[0]))
    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.