Brainhype

Brainhype is an esoteric programming language based on Brainfuck.

The instructions:

+	Increments the cell under the pointer.
-	Decrements the cell under the pointer.
<	Moves the pointer to the left.
>	Moves the pointer to the right.
,	Inputs a character to the current cell.
.	Outputs a character from the current cell.
[	While the current cell is nonzero...
]	End while.
{...}	Zeroes the current cell if the Brainhype program between the braces (no
I/O allowed), run on the current tape with the current pointer position, will
end at some point.

This language is "super-Turing-complete" because it solves the halting problem for Turing machines.

A Brainhype interpreter cannot be written in Brainhype: given some description of a Brainhype program on its tape, the interpreter can determine whether it halts or not. Therefore it is possible to build a program that, given some description of a Brainhype program on its tape, will determine whether that program, given its own description, will halt. This program will infinite loop if the given program will halt, and halt otherwise. Therefore, feeding this program its own description will result in it determining whether it itself will halt, and halting if and only if it does not halt. This is a contradiction, so a Brainhype interpreter written in Brainhype cannot exist. However, you can write a Brainhype interpreter in Scheme-omega.

See also: onoz

Example implementation

Written in CLooP.

// brainhype implementation in CLooP
// this probably breaks on invalid brainhype
// copyright never by no-one
// dedicated to Quintopia. Where's my fucking money, Quintopia?
 
#hyper;
int main(int[][] args) {
  // pull out args: first is the start tape, then the program, then the tape pointer, than the program pointer
  int[infinity] tape;
  pforeach(int p: 0 .. infinity) tape[p] = 0; // initialize
  pforeach(int p: 0 .. tape[0]#) tape[p] = tape[0][p]; // put in parameterized tape
  int[#int[1]] program = args[1];
  int tp = args[2][0];
  int pp = args[3][0];
 
  // now get goin'
  return run(tape, program, tp, pp, program#, -1);
}
 
int[] run(int[] tape, int[] program, int tp, int pp, int stop, int steps) {
  for ((steps == -1) ? infinity : steps) { // kind of a flaw in CLooP, imo!
    if (pp > stop) break; // i'm like 30% sure this does the right thing on invalid subprograms! that's pretty  good 
   
    if (program[pp] = '+') tape[tp]++;
    else if (program[pp] = '-') tape[tp]--;
    else if (program[pp] = '>') tp++;
    else if (program[pp] = '<') tp--;
    else if (program[pp] = '[') pp = (tape[tp] == 0) ? find(']', '[', program, pp, 1) : pp;
    else if (program[pp] = ']') pp = find('[', ']', program, pp, -1);
    else if (program[pp] = '{') if (halts(tape, program, tp, pp+1, find('}', '{', program, pp, 1))) tape[tp] = 0;
   
    pp++;
  }
  return tape;
}

int find(int a, int b, int[] program, int start, int step) {
  int depth = 0;
  foreach (int q: 0 .. infinity) { // ha ha broken on invalids
    int p = start + q*step;
    if (program[p] == b) depth++;
    else if (program[p] == a) depth--;
    if (depth == 0) return p;
  }
  return 0; // haaaaa ha
}

int halts(int[] tape, int[] program, int tp, int start, int stop) {
  int halted = false;
  pforeach(int p: 0 .. infinity) {
    run(tape, program, tp, start, stop, p); // for effect (i.e. halting)
    halted = true; // the potentially objectionable bit, but it's easily defined
  }
  return halted;
}