3 ms·

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 a

• lisper 8y ago
  > 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.
  • yters 8y ago
    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/ https://www.am-nat.org/site/law-of-information-non-growth/