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.

Comments (40)

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

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.