User:PkmnQ/Hypercomputable implementations

These are implementations for hypercomputable esolangs in "Banana pseudoPython". I hope to rewrite these in Banana Scheme at some later point, but I'll have to learn Scheme first.

Brainhype, Hyperon, and Loop preventing brainfuck

These implementations use pseudoPython-omega.

import collections, sys
def find_degree(code, open, close):
    max_nesting, nesting = 0, 0
    for instruction in code:
        if instruction in open:
            nesting += 1
        if instruction in close:
            nesting -= 1
        max_nesting = max(max_nesting, nesting)
    return max_nesting
def find_matches(code, open, close):
    matches, stack = {}, []
    for i, instruction in code:
        if instruction in open:
            stack.append(i)
        if instruction in close:
            match = stack.pop()
            matches[i], matches[match] = match, i
    return matches
# mostly adapted from [[brainfuck Python interpreter]]
def brainhype(code, tape=None, p=0):
    matches = find_matches(code, "[{", "]}")
    if tape is None:
        tape = collections.defaultdict(int)
    cp=0
    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]=='<':
            p-=1
        if code[cp]=='>':
            p+=1
        if code[cp]=='[':
            if not tape[p]:
                cp=matches[cp]
        if code[cp]==']':
            if tape[p]:
                cp=matches[cp]
        if code[cp]=='{':
            subprogram = code[cp+1:matches[cp]]
            if halts(find_degree(subprogram, "{", "}"), lambda: brainhype(subprogram, tape, p)):
                tape[p] = 0
            cp = matches[cp]
        cp+=1
def hyperon(code, tape=None, p=0):
    matches = find_matches(code, "[{", "]}")
    if tape is None:
        tape = collections.defaultdict(int)
    cp=0
    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]=='<':
            p-=1
        if code[cp]=='>':
            p+=1
        if code[cp]=='[':
            if not tape[p]:
                cp=matches[cp]
        if code[cp]==']':
            if tape[p]:
                cp=matches[cp]
        if code[cp]=='{':
            subprogram = code[cp+1:matches[cp]]
            if halts(find_degree(subprogram, "{", "}"), lambda: hyperon(subprogram, tape, p)):
                tape[p] += 1
            cp = matches[cp]
        cp+=1
def loop_preventing_brainfuck(code, tape=None, p=0):
    matches = find_matches(code, "([", "|")
    if tape is None:
        tape = collections.defaultdict(int)
    cp=0
    while cp<len(code):
        if code[cp]=='+':
            tape[p]=tape[p]+1
        if code[cp]=='-':
            tape[p]=tape[p]-1
        if code[cp]==',':
            c=sys.stdin.read(1)
            tape[p]=ord(c) if c else 0
        if code[cp]=='.':
            print(chr(tape[p]),end=)
        if code[cp]=='<':
            p-=1
        if code[cp]=='>':
            p+=1
        if code[cp]=='[':
            if not tape[p]:
                cp=matches[cp]
        if code[cp]=='|':
            if tape[p]:
                cp=matches[cp]
        if code[cp]=='(':
            subprogram = code[cp+1:matches[cp]]
            if halts(find_degree(subprogram, "([", "|"), lambda: loop_preventing_brainfuck(subprogram, tape, p)):
                loop_preventing_brainfuck(subprogram, tape, p)
            cp = matches[cp]
        cp+=1

Beeping cyclic tag

This implementation uses pseudoPython-2. If looping infinitely instead of erroring out is acceptable, pseudoPython-1 can be used instead.

import itertools

q1, q2, q = [], [], False

def run_until_beep(commands):
    global q1, q2, q
    while True:
        current_queue = q2 if q else q1
        if next(commands):
            if q1[0] == True:
                current_queue.append(next(commands))
                if q:
                    return
        elif next(commands):
            q = not q
        else:
            current_queue.pop(0)
            if q:
                return

def almost_beeping_cyclic_tag(commands):
    global q1, q2, q
    while halts(0, lambda: run_until_beep(commands)):
        run_until_beep(commands)
    return q2

def beeping_cyclic_tag(code, inputs=None):
    global q1, q2, q
    if inputs:
        q1 = inputs
    else:
        q1 = [True]
    commands = itertools.cycle(code)
    if halts(1, lambda: almost_beeping_cyclic_tag(commands)):
        return almost_beeping_cyclic_tag(commands)
    raise Exception("Q2 is updated infinitely")

Try to Take

This implementation uses pseudoPython-omega. The program is represented as follows:

• $I$ is represented as None.
• Variables $(x,y,z,...)$ are represented by numbers (each variable must be represented by a distinct number).
• $(\mathrm {term1} \ {\underset {variable}{M}}\ \mathrm {term2} )$ is represented by (variable, term1, term2) (where the variable is represented as the number that represents it and each term is represented in the given manner).

def find_degree(program):
    if program is None or type(program) is int:
        return 0
    _, term1, term2 = program
    return max(find_degree(term1), find_degree(term2)+1)
def try_to_take(program, variables=None):
    if variables is None:
        variables = {}
    if program is None:
        return 1
    if type(program) is int:
        return variables[program]
    variable, term1, term2 = program
    result = try_to_take(term1, variables)
    def find_nonzero():
        new_variables = {**variables, variable: 0}
        while (takeaway := try_to_take(term2, new_variables)) == 0:
            new_variables[variable] += 1
        return takeaway
    while result > 0 and halts(find_degree(program), find_nonzero):
        result -= find_nonzero()
    return result