Consider the halting set; … is not enumerable / computable. … Here, we should be careful with how we interpret “information”. After all, coNP-complete problems are trivially Cook reducible to their NP-complete counterparts (e.g., query the oracle and then negate the output), but many believe that there isn’t a corresponding Karp reduction (where we do a polynomial amount of computation before querying the oracle and returning its answer). Since we aren’t considering complexity but instead whether it’s enumerable at all, complementation is fine.
You’re using the word “enumerable” in a nonstandard way here, which might indicate that you’ve missed something (and if not, then perhaps at least this will be useful for someone else reading this). “Enumerable” is not usually used as a synonym for computable. A set is computable if there is a program that determines whether or not its input is in the set. But a set is enumerable if there is a program that halts if its input is in the set, and does not halt otherwise. Every computable set is enumerable (since you can just use the output of the computation to decide whether or not to halt). But the halting set is an example of a set that is enumerable but not computable (it is enumerable because you can just run the program coded by your input, and halt if/when it halts). Enumerable sets are not closed under complementation; in fact, an enumerable set whose complement is enumerable is computable (because you can run the programs for the set and its complement in parallel on the same input; eventually one of them will halt, which will tell you whether or not the input is in the set).
The distinction between Cook and Karp reductions remains meaningful when “polynomial-time” is replaced by “Turing computable” in the definitions. Any set that an enumerable set is Turing-Karp reducible to is also enumerable, but an enumerable set is Turing-Cook reducible to its complement.
The reason “enumerable” is used for this concept is that a set is enumerable iff there is a program computing a sequence that enumerates every element of the set. Given a program that halts on exactly the elements of a given set, you can construct an enumeration of the set by running your program on every input in parallel, and adding an element to the end of your sequence whenever the program halts on that input. Conversely, given an enumeration of a set, you can construct a program that halts on elements of the set by going through the sequence and halting whenever you find your input.
Thanks, my terminology was a little loose. What I was trying to hint at is that some of the paradox’s culling operations require uncomputable tests of English sentences, and that the regularity of the original language doesn’t determine the status of its subsets.
But that’s not what the puzzle is about. There is nothing about computability in it. It is supposed to be a paradox along Russell’s set of all sets that don’t contain themselves.
The response about formalizing exactly what counts as a set defined by an English sentence is exactly correct.
But there are more objections; even if “computability” isn’t explicitly mentioned in the problem, it’s still present. Are the sets “the singleton set containing 1 if and only if machine M halts on input w” and “the singleton set containing 1” the same? Even if we grant a procedure for figuring out what counts as a set, we can’t even compute which sentences are duplicates.
That still doesn’t make computability relevant until one introduces it deliberately. Compare to weaker notions than computability, like computability in polynomial time. Computability theory also complains the same once we have explicitly made definability subjective, and should have no more logical problems.
Saying that the problem is about computability because there is no computable solution proves too much: I could reply that it is about complexity theory because there is no polynomial-time solution. (In fact, there is no solution.)
We can build something like a solution by specifying that descriptions must be written in some formal language that cannot describe its own set of describables, then use a more powerful formal language to talk about that previous language’s set. For powerful enough languages, that’s still not computable, though, so computability theory wouldn’t notice such a solution, which speaks against looking at this through the lens of computability theory.
Sure, but how do we get the final set, then? The paradox addresses the reader in the imperative, implying one can follow along with some effective procedure to trim down the set. Yet if Turing’s thesis is to be believed, there is no such procedure, no final set, and therefore no paradox.
Computability is just \Delta^0_1 definability. There are plenty of other notions of definability you could try to cash out this paradox in terms of. Why pick \Delta^0_1 definability?
If the argument worked in any particular definability notion (e.g. arithmetic definability) it would be a problem. Thus, the solution needs to explain why the argument shouldn’t convince you that with respect to any concrete notion of definable set the argument doesn’t go through.
You’re using the word “enumerable” in a nonstandard way here, which might indicate that you’ve missed something (and if not, then perhaps at least this will be useful for someone else reading this). “Enumerable” is not usually used as a synonym for computable. A set is computable if there is a program that determines whether or not its input is in the set. But a set is enumerable if there is a program that halts if its input is in the set, and does not halt otherwise. Every computable set is enumerable (since you can just use the output of the computation to decide whether or not to halt). But the halting set is an example of a set that is enumerable but not computable (it is enumerable because you can just run the program coded by your input, and halt if/when it halts). Enumerable sets are not closed under complementation; in fact, an enumerable set whose complement is enumerable is computable (because you can run the programs for the set and its complement in parallel on the same input; eventually one of them will halt, which will tell you whether or not the input is in the set).
The distinction between Cook and Karp reductions remains meaningful when “polynomial-time” is replaced by “Turing computable” in the definitions. Any set that an enumerable set is Turing-Karp reducible to is also enumerable, but an enumerable set is Turing-Cook reducible to its complement.
The reason “enumerable” is used for this concept is that a set is enumerable iff there is a program computing a sequence that enumerates every element of the set. Given a program that halts on exactly the elements of a given set, you can construct an enumeration of the set by running your program on every input in parallel, and adding an element to the end of your sequence whenever the program halts on that input. Conversely, given an enumeration of a set, you can construct a program that halts on elements of the set by going through the sequence and halting whenever you find your input.
Thanks, my terminology was a little loose. What I was trying to hint at is that some of the paradox’s culling operations require uncomputable tests of English sentences, and that the regularity of the original language doesn’t determine the status of its subsets.
But that’s not what the puzzle is about. There is nothing about computability in it. It is supposed to be a paradox along Russell’s set of all sets that don’t contain themselves.
The response about formalizing exactly what counts as a set defined by an English sentence is exactly correct.
But there are more objections; even if “computability” isn’t explicitly mentioned in the problem, it’s still present. Are the sets “the singleton set containing 1 if and only if machine M halts on input w” and “the singleton set containing 1” the same? Even if we grant a procedure for figuring out what counts as a set, we can’t even compute which sentences are duplicates.
That still doesn’t make computability relevant until one introduces it deliberately. Compare to weaker notions than computability, like computability in polynomial time. Computability theory also complains the same once we have explicitly made definability subjective, and should have no more logical problems.
I don’t think I understand this line of objection; would you be willing to expand?
Saying that the problem is about computability because there is no computable solution proves too much: I could reply that it is about complexity theory because there is no polynomial-time solution. (In fact, there is no solution.)
We can build something like a solution by specifying that descriptions must be written in some formal language that cannot describe its own set of describables, then use a more powerful formal language to talk about that previous language’s set. For powerful enough languages, that’s still not computable, though, so computability theory wouldn’t notice such a solution, which speaks against looking at this through the lens of computability theory.
Sure, but how do we get the final set, then? The paradox addresses the reader in the imperative, implying one can follow along with some effective procedure to trim down the set. Yet if Turing’s thesis is to be believed, there is no such procedure, no final set, and therefore no paradox.
Computability is just \Delta^0_1 definability. There are plenty of other notions of definability you could try to cash out this paradox in terms of. Why pick \Delta^0_1 definability?
If the argument worked in any particular definability notion (e.g. arithmetic definability) it would be a problem. Thus, the solution needs to explain why the argument shouldn’t convince you that with respect to any concrete notion of definable set the argument doesn’t go through.
Turing’s thesis applies only to this notion of definability, right?
Yah, enumerable means something different than computably enumerable.