User:PkmnQ/Hypercomputable implementations
Jump to navigation
Jump to search
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(i) matches[i], matches[match] = match, i # 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")