3 ms·
That would indicate humans are partial halting oracles.
by yters 8y ago
That would indicate humans are partial halting oracles.
- lisper 8y agoNo. A partial oracle never gives a wrong answer, it's just allowed to say "I don't know."
- yters 8y agoAll 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 agoNo, 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 agoWell, 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 agoI 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 agoThat's true. But you originally said "wrong on an infinite number of problems".
- yters 8y agoYes, 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 agoThat 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 agoSorry, 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?
- TheOtherHobbes 8y agoIt's more likely to indicate that humans are irrational and easily confused.