RichardKennaway comments on A simple counterexample to deBlanc 2007? - Less Wrong

3 Post author: PhilGoetz 30 May 2011 05:09AM

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

Article Navigation

Comments (40)
Tags: fai math utility

Comments (40)

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

Comment author: PhilGoetz 30 May 2011 04:29:36PM *  0 points [-]

Because S_I is defined in the paper as the set of all total recursive functions compatible with the observations I. You cannot choose it to be anything else.

As I said, I am claiming to have a counterexample. I can choose any example out of all possible examples. You must show that the example I've chosen is not a possible case, to say that I'm not free to choose it.

S is not recursive, nor is it even recursively enumerable. That is, there is no Turing machine which, started on a blank tape, will output exactly all the members of S and no others. The same is true of S_I.

S is a subset of R, and R is the set of partial mu-recursive functions, meaning it consists of computable functions, meaning it is countable. R is enumerated by Goedel numbers; therefore it is enumerable. The elements of S_I are exactly those X for which p(X) > 0; and as I showed, they must be countable for this to occur. These are three separate proofs that S_I is countable in cardinality.

Constructing a Turing machine that generates S_I would be difficult. We don't have the information needed to do that. But saying that you don't know how to write that Turing machine, is not a proof that it does not exist.

S_I is of course countable, but there is no algorithm to calculate "the sum, over all possible worlds f in SI, of p(f)U(f(k))", because there is no way of enumerating SI, i.e. no computable bijection between S_I and N.

I've just demonstrated an example in which I provided a bijection between S_I and N, and computed the sum.

Comment author: RichardKennaway 31 May 2011 12:37:49PM 0 points [-]

Constructing a Turing machine that generates S_I would be difficult. We don't have the information needed to do that. But saying that you don't know how to write that Turing machine, is not a proof that it does not exist.

I am not saying that I don't know how, I am saying that it cannot be done. Of course, saying that it cannot be done is also not a proof that it does not exist, merely a claim that there is such a proof. So, here is such a proof.

Suppose S_I were recursively enumerable. This means that there is a function f from N to N such that (1) f is Turing-computable, (2) for all n, f(n) is the Gödel number of a Turing machine that computes a function in S_I, and (3) for every function in S_I there is an n such that f(n) computes that function.

Recall that S_I is, by definition, the set of total recursive functions that agree with the finite set of ordered pairs I.

Let g be the function from N to N that agrees with I, and such that for every integer n, g(n') = f(n)(n')+1, where n' is the nth integer that is not in the domain of I. Because f and I are total recursive, g is total recursive. Since g is consistent with I, g is in S_I. But g differs from f(n) for every n, contradicting hypothesis (3). Therefore S_I is not r.e.

Powered by Reddit Powered by Reddit