bftree

bftree is an esolang invented by User:None1, which uses an unrooted tree instead of a tape.

Tree

The tree has nodes, which contain a node number and value. The node number is only used for pointer movement.

The tree is defined using this syntax, at the start of the program: The first line contains a number, which is the number of nodes (node are numbered from 1 to node number), and the following lines contain two numbers, which define edges.

Commands

The commands are the same as brainfuck, except for the pointer moving commands.

In bftree, the command to move the pointer from one node to the other is *integer*, which moves the pointer to its ((integer-1) mod k)+1-th (k is the number of adjacent nodes) smallest adjacent node.

bfgraph

The author quickly realized that the data structure can be extended to a graph, in which case the first line contains two numbers: node number and edge number.

Examples

Print HI!

bftree

4
1 2
2 3
3 4
++++++++[*2*+++++++++*1*-]*2*.+.*2*++++++++[*2*++++*1*-]*2*+.

bfgraph

4 3
1 2
2 3
3 4
++++++++[*2*+++++++++*1*-]*2*.+.*2*++++++++[*2*++++*1*-]*2*+.

Interpreters

bftree

Python

# Cell values are within [0,256) in this implementation, as such, this implementation is not TC
import sys
from time import sleep
n=int(input().strip())
a=[[]for i in range(n+1)]
for i in range(n-1):
    x,y=map(int,input().split())
    a[x].append(y)
    a[y].append(x)
for i in range(1,n+1):
    a[x].sort()
def bf(code):
    s=[]
    matches={}
    tape=[0]*1000000
    for i,j in enumerate(code):
        if j=='[':
            s.append(i)
        if j==']':
            m=s.pop()
            matches[m]=i
            matches[i]=m
    cp=0
    p=1
    while cp<len(code):
        if code[cp]=='+':
            tape[p]=(tape[p]+1)%256
        if code[cp]=='-':
            tape[p]=(tape[p]-1)%256
        if code[cp]==',':
            c=sys.stdin.read(1)
            tape[p]=(ord(c) if c else 0)%256
        if code[cp]=='.':
            print(chr(tape[p]),end='')
        if code[cp]=='*':
            cp+=1
            s=0
            while code[cp]!='*':
                s=s*10+int(code[cp])
                cp+=1
            p=a[p][(s-1)%len(a[p])]
        if code[cp]=='[':
            if not tape[p]:
                cp=matches[cp]
        if code[cp]==']':
            if tape[p]:
                cp=matches[cp]
        cp+=1
bf(sys.stdin.read())

bfgraph

Python

# Cell values are within [0,256) in this implementation, as such, this implementation is not TC
import sys
from time import sleep
n,m=map(int,input().split())
a=[[]for i in range(n+1)]
for i in range(m):
    x,y=map(int,input().split())
    a[x].append(y)
    a[y].append(x)
for i in range(1,n+1):
    a[x].sort()
def bf(code):
    s=[]
    matches={}
    tape=[0]*1000000
    for i,j in enumerate(code):
        if j=='[':
            s.append(i)
        if j==']':
            m=s.pop()
            matches[m]=i
            matches[i]=m
    cp=0
    p=1
    while cp<len(code):
        if code[cp]=='+':
            tape[p]=(tape[p]+1)%256
        if code[cp]=='-':
            tape[p]=(tape[p]-1)%256
        if code[cp]==',':
            c=sys.stdin.read(1)
            tape[p]=(ord(c) if c else 0)%256
        if code[cp]=='.':
            print(chr(tape[p]),end='')
        if code[cp]=='*':
            cp+=1
            s=0
            while code[cp]!='*':
                s=s*10+int(code[cp])
                cp+=1
            p=a[p][(s-1)%len(a[p])]
        if code[cp]=='[':
            if not tape[p]:
                cp=matches[cp]
        if code[cp]==']':
            if tape[p]:
                cp=matches[cp]
        cp+=1
bf(sys.stdin.read())

Computational class

When node values have a limited bound, the esolang is not Turing complete because it doesn't have infinite memory.

When node values are unbounded, the esolang is Turing complete as it can be translated from 3 cell brainfuck, assuming that the pointer never goes out of bounds.

We can construct a tree like this:

3
1 2
2 3

We can use *1* for <: If the pointer is on node 2, it goes to cell 1. If the pointer is on node 3, it goes to cell 2. We can use *2* for >: If the pointer is on node 1, it goes to cell 2. If the pointer is on node 3, it goes to cell 3.

brainfuck with more cells but infinite cell value can be translated this way by simply constructing a chain with more nodes.