AlephNeil 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: PhilGoetz 30 May 2011 02:56:17PM *  0 points [-]

Why would I not have a free choice of S_I when constructing a counterexample? Remember that a counterexample is one particular case, taken out of all possible cases that a theorem applies to.

The only reason I would not have a free choice of S_I, is if each application of the theorem is meant to apply to all possible choices of S_I. That would mean that the theorem is actually proving that, for any unbounded utility function U, there exists some set of possible worlds for which it does not converge. That would be a still-interesting, but much weaker result.

Gödel numbering is used to enumerate R, the set of all partial recursive functions. R includes S and S_I, but neither S nor S_I is enumerable (by unsolvability of the halting problem).

Sorry; I believe you are incorrect, for the two reasons given in my post. Think about it: Goedel numbers are integers; how could anything that is enumerated by Goedel numbers not be enumerable? S_I, S, and R are all enumerable. The original paper says that R is the set of partial mu-recursive functions, which means computable functions; and the number of computable functions is enumerable.

EDIT: As AlephNeil noted, I meant that R is countable. "Neither S nor S_I is enumerable (by unsolvability of the halting problem)" is not supported by any argument. Nor does whether it is enumerable or not affect anything in my original post.

Comment author: AlephNeil 30 May 2011 03:28:09PM 4 points [-]

Goedel numbers are integers; how could anything that is enumerated by Goedel numbers not be enumerable? S_I, S, and R are all enumerable. The original paper says that R is the set of partial mu-recursive functions, which means computable functions; and the number of computable functions is enumerable.

You seem to be using 'enumerable' to mean 'countable'. (Perhaps you're confusing it with 'denumerable' which does mean countable.)

RichardKenneway means "recursively enumerable".

Comment author: PhilGoetz 30 May 2011 04:40:32PM *  0 points [-]

You're right! But I may still be right that the set of functions in R is enumerable. (Not that it matters to my post.)

There is a Turing function that can take a Goedel number, and produce the corresponding Goedel function. If you can define a programming language that is Turing-complete, and for which all possible strings are valid programs, then you just turn this function loose on the integers, and it enumerates the set of all possible Turing functions. Can this be done?

Comment author: AlephNeil 31 May 2011 11:56:06AM 1 point [-]

Sure, R is recursively enumerable, but S and S_I are not.