Talk:Brainhype

I see two possibilities here. Either A) It doesn't actually solve the halting problem or B) It's impossible to interpret. For it to solve the halting problem, it would have to examine but not run the contents of the {}, and return whether it halts or not, to do so would be impossible because it would be impossible to simply examine the code without running it, and so would have to run the code and go into an infinite loop if it didn't halt. Or am I mistaken? --GregorR 23:12, 19 Oct 2005 (GMT)

You aren't, but there's a third possibility: C) Brainhype programs only have access to a limited number of cells, like the 30000 of the original compiler. Then Brainhype is a finite state machine and loops can be detected in a finite amount of time by comparing each state against every previous state; if there is a match, the program will not halt. With more than a few cells, however, it would take an impractical amount of time and memory space to do this, so it would be impossible to interpret in real life. Possibility D: This article should be categorized under "Joke languages". --Graue 00:10, 20 Oct 2005 (GMT)

I was thinking B when I first thought up this language, then I added alternative A. (C is just a subset of A, isn't it?) --Ihope127 15:02, 20 Oct 2005 (GMT)

So far as I can see, the language is well-defined, but it isn't possible to implement it using a Turing-machine. Is this really a problem though? Gravity can't be implemented on a Turing-machine either because the equations, while well defined, are non-computable. Perhaps there should be a new category for languages like this? I'm not sure what it should be called - perhaps 'Non-computable languages'. --Safalra 16:48, 20 Oct 2005 (GMT)

Exactly. I wanted a language that was well-defined but could compute the uncomputable, even if the language itself had to be uncomputable (and, indeed, it did have to be). --Ihope127 00:53, 21 Oct 2005 (GMT)

I haven't looked closely at Gravity, but the couple of "languages" of this type that I did look at cannot exist (even theoretically), because they are self-contradictory (see the section below on halting-oracles). The contradiction is removable by changing them to be "oracle-based" or "oracular" languages, whose programs generally cannot be interpreted in a Turing-equivalent langauge. --r.e.s. (Talk) 20:50, 8 December 2007 (UTC) Strike that — my apologies for the mistake (discussion below). --r.e.s. (Talk) 03:05, 10 December 2007 (UTC)

BTW, "non-computable language" is a poor choice of terminology, imo, because even an "oracular" programming language (which is not interpretable in a Turing-equivalent language) is still a computable language, i.e. a computable set of programs.--r.e.s. (Talk) 21:08, 8 December 2007 (UTC)

What's the halting problem? --Aardwolf 10:58, 20 Oct 2005 (GMT)

Wikipedia: Halting problem --BodyTag 11:50, 20 Oct 2005 (GMT)

I'll make a stub on esolang about the halting problem, since it has to do with computation. --Aardwolf 12:10, 20 Oct 2005 (GMT)

Maybe you can make it to interpret itself by making input and output commands doing something inside { } blocks. Maybe input and output would be piped through consecutive { } blocks (even if they aren't right next to each other). I'm not sure if this work, but try. --Zzo38 16:41, 10 May 2006 (UTC)

Are you proposing to add I/O inside braces? In Brainhype right now, it ain't happening. --Ihope127 23:59, 6 Sep 2006 (UTC)

There are many possible variations there. One way I thought of is to change the definition of {} to:

{...}	If the Brainhype commands between the braces would end at some point, they are performed. Otherwise, it has no effect.

This would allow batch I/O at least (where all input is known at the beginning). I don't yet see a way to allow interactive I/O inside braces, since you would need to know the input in order to know whether to read it... --Ørjan 18:17, 8 Sep 2006 (UTC)

You could do 2 things, one is to make it so only batch I/O is possible, the other is when the {} block is finish (in case it does halt and execute), it will change back the state of the tape how it was before (if that is how it is supposed to work, I think it is) and then set the current cell to zero. --Zzo38 18:12, 9 December 2007 (UTC)

Turing degree

I don't think this actually fits into any one Turing degree, but I think it can compute anything that 0, 0', 0'', etc. can, and nothing that they can't. In this way I suppose you could see it as their limit.

The language cannot exist as specified (see the section below), as the spec leads to a logical contradiction. Nonexistent languages can have amazing computational power :) --r.e.s. (Talk) 20:09, 8 December 2007 (UTC) Strike that — my apologies for the mistake (discussion below). --r.e.s. (Talk) 03:05, 10 December 2007 (UTC)

A "joke language", but easily modified to make {...} a halting-oracle for brainfuck

The Brainhype language is specified as being able to solve the halting problem for Brainhype programs (a logical impossibility), so it is necessarily a "joke language". The proof of impossibility is by contradiction: Assume the language exists as specified — i.e., for any Brainhype program P, the spec implies {P} can decide whether P halts on its own index — in which case there is some Brainhype program that computes the following total function H from N to N:

H(n) ::= if P_n(n) halts then 1 else 0

where P_n is the n^th program in an enumeration of all Brainhype programs. Consequently, if the language exists as specified, there is a Brainhype program, say P_q, that computes the following partial function Q:

Q(n) ::= if H(n)=1 then UNDEF else 0

where UNDEF is the partial function computed by an infinite loop (i.e. undefined for all n). Therefore, the very *specification* of Brainhype implies that exactly one of the following two cases must hold, which is a contradiction:

Q(q)=UNDEF and H(q)=1 (by construction of Q) and H(q)=0 (by definition of H), or

Q(q)=0 and H(q)=0 (by construction of Q) and H(q)=1 (by definition of H).

In other words, the language is specified in such a way that it cannot exist. Q.E.D.

Similar remarks apply to every "language" specified as capable of solving its own halting problem (e.g., You are Reading the Name of this Esolang, etc.) — they should be classified as "joke languages", unless modified to remedy the logical impossibility.

Likewise, the above section on "Turing degrees" is misguided. A good way to see this is to compare the situation to TMs-with-oracle_A (which are not TMs). No TM can solve the halting problem for TMs, but there is a theoretical provision for an oracle_A (which is not a TM) to do so. However, the set of all such TMs-with-oracle_A now has its own halting problem that's unsolvable by every member of that set, and so on.

Brainhype could be modified to be a TM-plus-oracle analog by simply changing the spec to say that only a brainfuck program is allowed in the curly brackets {...}, so {...} is then a halting-oracle for brainfuck programs, with no logical contradiction. (Similarly, You are Reading the Name of this Esolang is easily freed of contradiction by specifying that only Spoon programs are allowed between its []-brackets, making [...] a halting-oracle for Spoon programs.)

--r.e.s. (Talk) 19:51, 8 December 2007 (UTC)

I don't see the problem with You are Reading the Name of this Esolang, at least. Whatever is inside square brackets has to be hard-coded, so if a Spoon oracle is available the program can be parsed and executed simply by expanding the brackets from inside to outside, because nothing more complicated than a Spoon program is being checked for haltingness at each stage. The diagonalisation argument doesn't prove that the language can solve its own halting problem (known to be impossible); instead, it shows that one of the assumptions made above is false, in this case the assumption that it's possible to write a You are Reading the Name of this Esolang self-interpreter; you have proved that this is false, because if it were true then the argument above would prove the impossibility of the language. --ais523 11:25, 9 December 2007 (UTC)

Brainhype is the same, it is not contradictory because the program whose halting problem is solved must be textually included, so must have a lower {} nesting level. In particular even with clever encoding, a Brainhype partial self-interpreter must fail on some programs with higher nesting levels of {}, and the H function cannot be constructed. --Ørjan 16:15, 9 December 2007 (UTC)

Self-interpretation isn't the issue, in the sense that there is no interpreter of any kind that can execute Brainhype according to its spec. The Brainhype spec implies that {P} can decide whether P halts on its own index, where P is an arbitrary Brainhype program, and that is a logical impossibility. The same holds for [P] in You-are-Reading, where P is an arbitrary Y-a-R program. Hence, neither Brainhype nor You-are-Reading can exist as it is currently specified. If the idea is just to explore languages whose programs have elements that are not Turing-computable, then the modified versions I described satisfy that without being self-contradictory. --r.e.s. (Talk) 17:12, 9 December 2007 (UTC)

You can't nest infinitely. P has to be a program with a lower nesting level than {P} and you could indicate nesting levels such as brainhype(0) = brainfuck, brainhype(1) = the program checks for halting of brainfuck programs, brainhype(2) = check if a brainhype(1) program halts or not, etc --Zzo38 18:12, 9 December 2007 (UTC)

"Nesting infinitely" has nothing to do with this. The P in {P} or [P] is supposed to be an arbitrary program (as such, possibly containing brackets of the respective kinds, but necessarily of finite length). --r.e.s. (Talk) 18:42, 9 December 2007 (UTC)

Self-interpretation was only an aside, really. The point is: P has to be literally contained in the original program. So to make a program to compute H you would have to include all of the P_n(n), giving an infinite program. The contradiction of the halting problem only appears if every program can be given as input to the same halting checking program. --Ørjan 20:28, 9 December 2007 (UTC)

That's mistaken — the contradiction originates in the spec itself, because the spec implies {P} can decide whether an arbitrary P halts on its own index. If in fact there are no means at all by which it can do this (and there are none, because it's a logical impossibility), then the spec is vacuous. --r.e.s. (Talk) 21:37, 9 December 2007 (UTC)

I am convinced there is no contradiction. It is impossible to create a program that decides for all n whether P_n(n) halts, because there is a missing leap from a program that decides whether a fixed P halts on its own index to a program that decides whether a computed P does so. This is because a Brainhype program can only use its halting decision powers on textually included subprograms. Brainhype does not have sufficient power to decide the halting of a program computed or read from input - it lacks the reflection necessary to compose and run enough other Brainhype programs. --Ørjan 22:44, 9 December 2007 (UTC)

That does not address the issue: It is logically impossible for a Brainhype program to decide (as the spec implies {P} does) whether P halts on its own index, where P is an arbitrary Brainhype program; consequently, the spec is vacuous. It's like specifying that there's a command which, when executed, returns a prime number between eight and ten. --r.e.s. (Talk) 23:06, 9 December 2007 (UTC)

Is not. Your step asserting there is a program that can compute H for all n is incorrect, it does not follow from the ability to construct a program that checks a given P. --Ørjan 00:02, 10 December 2007 (UTC)

You seem to be misunderstanding the proof-step, which is that if the language is as specified, then, according to those specs, a Brainhype program can decide, via {P}, whether P halts on its own index, where P is an arbitrary Brainhype program — that's what the specs say is the operational meaning of the curly brackets. And that's a logical impossibility. --r.e.s. (Talk) 00:55, 10 December 2007 (UTC)

One more time... for each P, I acknowledge that there exists a Brainhype program containing {P} which can decide whether P halts on its own index. However, there does not exist a Brainhype program such that for every P, that program can decide whether P halts on its own index, because such a program would have to contain an infinite number of programs of the form {P} as substrings. --Ørjan 01:45, 10 December 2007 (UTC)

---

THANK YOU for the patient replies — Ørjan's last one makes my error perfectly glaring — it's embarassing to have made such a "beginner's mistake". My apologies to everyone. --r.e.s. (Talk) 02:51, 10 December 2007 (UTC)

---

Whew, I was just about to give up... :) --Ørjan 11:45, 10 December 2007 (UTC)

ais523 wrote: "The diagonalisation argument doesn't prove that the language can solve its own halting problem (known to be impossible) ..." On the contrary, that's exactly what the diagonalisation argument does prove as part of the reductio ad absurdum, and the proof above is just one of those that allows your conclusion of "known to be impossible". Since you admit it is known that no Turing-complete language can solve its own halting problem, surely you can see that assuming it to be possible, as these languages do, makes them self-contradictory. --r.e.s. (Talk) 19:22, 9 December 2007 (UTC)

Sorry, that sentence was ambiguous. The meaning I intended was "the diagonalisation argument you gave would, if based on valid premises, prove that the language could solve its own halting problem (and this is known to be impossible), but does not prove this because one of the premises is invalid". I can see how you could have misinterpreted what I wrote, though, and I apologise for being unclear. --ais523 09:22, 10 December 2007 (UTC)

But without I/O it would be impossible to feed it its own description...

... Immibis 03:55, 6 July 2008 (UTC)

And I/O wouldn't help any as the language isn't self-modifying or anything, the program which termination is being checked has to be written inside {} in the very program that is ran in the interpreter. So yeah, there shouldn't be any way to construct a program that would even start checking its own termination. But as for any possible program string A, it should be possible to check whether they terminate or not, just by making another program B, which would have the code "{A}" somewhere in it. Or not? --Keymaker 10:44, 6 July 2008 (UTC)