4 ms·

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 ca

by yters 8y ago

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.

dragonwriter 8y ago
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.)
- yters 8y ago
  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.
lisper 8y ago
> 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).
- yters 8y ago
  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.
  - lisper 8y ago
    That's true. But you originally said "wrong on an infinite number of problems".
    - yters 8y ago
      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.
      - lisper 8y ago
        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.
        yters 8y ago
        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?
        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.

by yters 8y ago

dragonwriter 8y ago

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.)

yters 8y ago
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.

lisper 8y ago

> 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).

yters 8y ago
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.
- lisper 8y ago
  That's true. But you originally said "wrong on an infinite number of problems".
  - yters 8y ago
    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.
    - lisper 8y ago
      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.
      - yters 8y ago
        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?
        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.