Is the difference between "whether or not" and "if" trivial in english (I'm French) ? I think I understand the third point in the Caveats section. However I only understand the last sentence from context. Is there already an explanation on Arbital of the difference between "whether or not" and "if" as used here ?
This is not universally agreed-upon, but I use "A decides whether or not B holds" to mean "A outputs 1 if B holds, and outputs 0 otherwise".
If I said "A decides if B holds", I would consider that ambiguous: it might mean "A outputs 1 if B holds" without the requirement on A's behaviour if B doesn't hold.
Surely they are equivalent. Given a Rice-deciding oracle, we can ask the oracle, "Does the partial function defined by machine [n] specify where input k should go?"; that determines whether [n] halts on input k or not.
The problem I have in mind is deciding whether the Halting problem is equivalent to any statement of the form "You cannot decide membership for S", where S is a non-trivial set of computable functions.
Clearly the argument exposed above shows that the Halting problem implies any of these statements, but does the reverse implication hold directly? In my proof of how Rice implies Halting I am handpicking an S. Can we make do without the handpicking?
In other words, given a Halting oracle, can we make a Rice oracle for an arbitrary S?
Is the difference between "whether or not" and "if" trivial in english (I'm French) ? I think I understand the third point in the Caveats section. However I only understand the last sentence from context. Is there already an explanation on Arbital of the difference between "whether or not" and "if" as used here ?
This is not universally agreed-upon, but I use "A decides whether or not B holds" to mean "A outputs 1 if B holds, and outputs 0 otherwise".
If I said "A decides if B holds", I would consider that ambiguous: it might mean "A outputs 1 if B holds" without the requirement on A's behaviour if B doesn't hold.
Surely they are equivalent. Given a Rice-deciding oracle, we can ask the oracle, "Does the partial function defined by machine [n] specify where input k should go?"; that determines whether [n] halts on input k or not.
I think the answer is no. Indeed, there are uncountably many S, but only countably many machines which can access oracles.
The problem I have in mind is deciding whether the Halting problem is equivalent to any statement of the form "You cannot decide membership for S", where S is a non-trivial set of computable functions.
Clearly the argument exposed above shows that the Halting problem implies any of these statements, but does the reverse implication hold directly? In my proof of how Rice implies Halting I am handpicking an S. Can we make do without the handpicking?
In other words, given a Halting oracle, can we make a Rice oracle for an arbitrary S?
I think the halting problem probably should have its own page, rather than being linked to the umbrella uncomputability page.