Hacker News Reader

Comment by lisper | Hacker News Reader

I find this argument very unconvincing. The reason code has bugs is precisely because humans are NOT good halting oracles. We're not even good self-assessors of our own oracular capabilities because we not only write buggy code, but we're often surprised by the bugs in the code we write.

View on HN

Could it be that 'untrained' humans are NOT good halting oracles? the trained ones are good-enough halting oracles i.e on the scale of a fully focused Euler

That would indicate humans are partial halting oracles.

No. A partial oracle never gives a wrong answer, it's just allowed to say "I don't know."

All a partial oracle has to do is be able to correctly answer an undecidable set of problems and then it can no longer be replicated by a Turing machine. It can be wrong on an infinite number of problems and still fit this requirement.

No, a partial oracle by definition gives correct results for some subset of questions in the domain of interest, and no answer for other questions in the domain. It never gives wrong answers. (Now, if you can define the scope of questions for which a procedure gives wrong answers such that you can identify them in advance, you can convert it to a partial or full oracle by applying a process around the base procedure that flips the answer for those question (for a binary domain, like halting) or converts them to “don't know” (for non-binary domains.)

Well, if it's a definition thing, we can define a "splurg" which can give correct answers for an undecidable subset, and arbitrary answers, some wrong some right, for everything else. A "splurg" cannot be a TM, but it is also not a complete oracle.

> It can be wrong on an infinite number of problems and still fit this requirement.

Nope. If it's allowed to be wrong, then a TM can do it. In fact, any one-bit hash function is a partial oracle on that definition (which is the reason that definition is not used).

I don't follow your reasoning. If we take the set of problems a complete halting oracle can correctly decide, and set one problem to an incorrect answer, a normal TM still cannot correctly decide this reduced set. This example seems to contradict what you are saying.

That's true. But you originally said "wrong on an infinite number of problems".

Yes, that seems to be correct as well, right? We subtract an infinite number of problems from the undecidable set, and it is still an undecidable set and cannot be generated by a TM.

That would be true if you got to pick which problems you were removing from the set, but you don't. If you knew which problems the oracle was going to get wrong, then you would know the right answers to all of them because there are only two possible answers.

A hash function will get an infinite number of answers right and an infinite number of answers wrong. But because you don't know which is which, the result is useless.

Sorry, I'm not communicating clearly. What I am saying is there is an undecidable infinite set of correct answers, and then another infinite set of arbitrary answers. In the second set, there are an infinite number of right and wrong answers. The first set cannot be replicated by a TM and the second set can. Combining the sets into one and we get a set that a TM cannot replicate, yet it still has an infinite number of arbitrary wrong answers. This seems possible to me. Am I missing something?

> Sorry, I'm not communicating clearly.

Indeed not.

> there is an undecidable infinite set of correct answers

The term "undecidable set" has a technical meaning, which I'm pretty sure is not what you intended here. The technical meaning of "an undecidable set" is a set for which the question of whether a given thing is a member of the set is undecidable. So, for example, the set of all halting TM programs is an undecidable set.

But the set you are specifying here is not a set of programs, it is (you say) a set of answers. Answers to what? I presume you mean "answers to the halting problem". But what does that mean? There are only two "answers to the halting problem": HALT and RUN-FOREVER, and that's a finite set with two elements. Your set is "infinite" so that's obviously not what you meant.

Maybe you meant a set of ordered pairs consisting of a program P and an element of { HALT, RUN-FOREVER } corresponding to whether P halts or runs forever, where the ordered pair is a member of the "correct" set only if P halts if the second element of the pair is HALT, or if P runs forever if the second element of the pair is RUN-FOREVER. You didn't actually specify it, but I presume you want a given P to appear either in the "correct" set or the "arbitrary" set but not both, so the membership condition in "correct" has to be "only if" and not "if and only if". You also didn't specify whether a pair (P, HALT) and (P, RUN-FOREVER) can both appear in the "arbitrary" set, though I presume the answer to that is "no".

So what about the other direction? Your "arbitrary" set also includes some pairs that meet the criterion for membership in the "correct" set (an infinite number, actually, by your own stipulation). So what determines what goes into the "correct" set and what goes into the "arbitrary" set?

But all of this is still missing the main point: what makes a partial oracle interesting is not that it's allowed to be wrong -- it isn't. It's that it is allowed to give "I don't know" as an answer.

It is actually possibly to define a coherent concept of an oracle that is allowed to be wrong, but these are not called "partial oracles", they are "probabilistic oracles". There's a whole field of study of algorithms that act like probabilistic oracles, called "probably approximately correct" or PAC. There are also "random oracles" which are kind of like probabilistic oracles, and which are useful in cryptography. But that's not what is under discussion here.

Yep, your ordered pair scenario is what I'm saying. The correct set is undecidable in that it would take an infinitely large TM to correctly identify all the pairs, so it is not possible to characterize the set with a finite TM. The arbitrary set is labeled with a random oracle, or perhaps with an oracle that outputs HALT for every program, or it just says "I don't know."

This seems coherent and to capture the notion of a PHO. All of this to point out that the fact humans cannot figure out every math problem does not mean they can be reduced to some sort of finite TM, so that standard objection against the halting oracle idea fails.

Here's a proof of the idea, demonstrating a partial halting oracle can violate the law of information non-growth:

https://www.am-nat.org/site/law-of-information-non-growth/

It's more likely to indicate that humans are irrational and easily confused.

Reply on news.ycombinator.com