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