Less Wrong is a community blog devoted to refining the art of human rationality. Please visit our About page for more information.

# Tyrrell_McAllister comments on But Somebody Would Have Noticed - Less Wrong

35 04 May 2010 06:56PM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

## Comments (250)

Sort By: Best

You are viewing a single comment's thread. Show more comments above.

Comment author: 06 May 2010 12:11:39AM 2 points [-]

To find X that satisfy Russell's paradox, you would have to violate the rule you just stated.

Do you mean that I can't verify that a set is not an element of itself? But the empty set, for example, is not an element of itself. I can confirm this by noting that no thing is an element of the empty set (which is a finite check). Hence, the empty set, in particular, is not an element of the empty set. Therefore, by setting X = the empty set, I have an X such that X is not an element of X.

Note that in the above use of the predicate not(member(X,X)), both occurrences of 'X' were bound. So I'm not sure what you mean when you say that I "would have to violate the rule [I] just stated."

Comment author: 06 May 2010 01:46:59AM *  -2 points [-]

Oops, you're right. I was thinking of cases where you are trying to generate answers to a query, which is different from testing one candidate answer.

Let me start over:

My suspicion, which I haven't proved, is that Russell's Paradox is a result of specifying a logic, and not specifying the algorithms used to evaluate statements in that logic or to answer queries. In any complete specification of a logic, including both the rules and the computational steps taken to evaluate or query-answer, you will probably find that you can prove what the outcome of the Russell's paradox query is.

In other words, "formal logic" is too sloppy; my intuition is that in Russell's paradox, it hides problems with order of execution.

Comment author: 06 May 2010 01:56:29AM 2 points [-]

Not really. In most standard axiomatic descriptions of set theory, like say ZFC, one doesn't need to think at all about computability of set relations. This is a good thing. We want for example the Busy Beaver function to be well-defined. And we want to be able to talk about things like the behavior of Turing machines when connected to non-computable oracles. If we insist that our set theoretic relationships be computable this sort of thing becomes very hard to talk about.

Comment author: 07 May 2010 07:53:01PM *  -1 points [-]

Huh? The Busy Beaver function is all about computability. The function itself is not computable; but you know that only because you've spelled out how the computation works, and can show that there is an answer but that it is not computable.

ZFC was designed to avoid Russell's Paradox; it does this by getting closer to a computable description of set theory. The definition itself is actually computational; a set of axioms of implication are just rewrite rules. It is ambiguous only in that it fails to specify what order rewrite rule applies first.

I have no problem with using non-computable oracles. But the way Turing machines interact with those oracles is computationally explicit. The view I'm expressing suggests you could run into troubles if you posed an oracle a question that hid ambiguities that would be resolved by a computational specification of the oracle. But I've never seen any use of an oracle that did that. People don't use oracles for Russell's paradox-like problems; they typically use them for non-computable functions.

Comment author: 07 May 2010 07:55:25PM 0 points [-]

How are you defining computable? Naively I would think it would be something like describable by a Turing machine that outputs the result after finite time. But Busy Beaver won't do that. There may be definitional issues at work here.

Comment author: 08 May 2010 02:25:16AM -1 points [-]

The busy beaver function isn't computable; but it is posed within a well-defined computational model.

Comment author: 08 May 2010 07:56:49PM 0 points [-]

Ok. So when do you consider something to be within an acceptable computational model or not?