Can you find any reason why this is not a counterexample?
The only step I’m suspicious of is the step where I choose the set of possible worlds.
Yes. You don’t have a free choice of S_I. (Excuse the TeXisms—I don’t know of a way of getting subscripts and superscripts in a comment.) S_I is defined to be the subset of S that is consistent with observations so far, and S is the set of all total recursive functions from N to N (section 2 of the paper). H, the set of hypotheses, is a set of total functions from N to N that is required to include all of S_I.
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).
S_I contains functions big enough and early enough in the enumeration that unless your utility function tends to zero uncomputably fast, it is blown up by the Busy Beaver.
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.
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.)
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?
Why would I not have a free choice of S_I when constructing a counterexample?
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.
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).
That was a sloppily expressed statement on my part. What is the case and I should have expressed is that:
R is (encoded by) a recursive set of integers: those integers that are Gödel numbers of partial-recursive functions from N to N. That it is recursive means that there is a Turing machine that can decide for any integer whether it is in R or not.
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.
The fact that the possible rate of growth of the function defined by the n’th member of S_I grows with n faster than any computable function is what makes the proof work.
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.
I hope my restatement clarifies the matter. S_I is of course countable, but there is no algorithm to calculate “the sum, over all possible worlds f in S_I, of p(f)U(f(k))”, because there is no way of enumerating S_I, i.e. no computable bijection between S_I and N. This in turn prevents this utility function from being computable, and as Peter de Blanc’s paper shows, it cannot even be bounded below by a computable function.
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 S_I, of p(f)U(f(k))”, because there is no way of enumerating S_I, 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.
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.
A counterexample to what? Peter de Blanc defines exactly what he means by S_I. Replacing S_I by something completely different and calling that S_I does not make a counterexample to what he proves. It may be an example of something worth proving; he himself suggests this at the end of his 2009 paper:
We could use a smaller hypothesis space; perhaps not all computable environments should be considered.
This is supposed to be a counterexample. A counterexample means you are allowed to select any possible case. This is one possible case. I am not “replacing S_I by something completely different.” I am choosing one possible S_I. If you don’t like my choice of S_I, you need to show that it is not a possible case. That would include showing that I have chosen an S_I that is inconsistent with my earlier choices. Try to do that.
If I had specified the set of observations I, then also specified S_I in a way not determined by I, then you could make that argument. As I have not specified I, you need to show that my choice of S_I is inconsistent with any possible set I in order to make the argument you’re trying to make.
Let J be the constant set that I is currently equal to. Your agent’s set of hypotheses then does not contain the computable function f(k) =
(2(1-1/2^k))^4 for all K in J
-k for all K not in J
By construction, this hypothesis must be compatible with the known input-output pairs, since it is indistinguishable from your f_4 given the observations in J. S_I must therefore contain f iff it contains f_4. Your S_I does not satisfy this, so it is not a counterexample.
Suggestion: treat yourself to a second piece of chocolate and add an ETA at the top of the post—the parent comment is buried too deeply in the thread, for informational purposes.
As I have not specified I, you need to show that my choice of S_I is inconsistent with any possible set I in order to make the argument you’re trying to make.
In the original paper, S_I is determined by I. There is no I for which your set S_I is the set defined in the paper. It really is as simple as that.
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.
Yes. You don’t have a free choice of S_I. (Excuse the TeXisms—I don’t know of a way of getting subscripts and superscripts in a comment.) S_I is defined to be the subset of S that is consistent with observations so far, and S is the set of all total recursive functions from N to N (section 2 of the paper). H, the set of hypotheses, is a set of total functions from N to N that is required to include all of S_I.
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).
S_I contains functions big enough and early enough in the enumeration that unless your utility function tends to zero uncomputably fast, it is blown up by the Busy Beaver.
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.
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.
You seem to be using ‘enumerable’ to mean ‘countable’. (Perhaps you’re confusing it with ‘denumerable’ which does mean countable.)
RichardKenneway means “recursively enumerable”.
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?
Sure, R is recursively enumerable, but S and S_I are not.
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.
That was a sloppily expressed statement on my part. What is the case and I should have expressed is that:
R is (encoded by) a recursive set of integers: those integers that are Gödel numbers of partial-recursive functions from N to N. That it is recursive means that there is a Turing machine that can decide for any integer whether it is in R or not.
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.
The fact that the possible rate of growth of the function defined by the n’th member of S_I grows with n faster than any computable function is what makes the proof work.
I hope my restatement clarifies the matter. S_I is of course countable, but there is no algorithm to calculate “the sum, over all possible worlds f in S_I, of p(f)U(f(k))”, because there is no way of enumerating S_I, i.e. no computable bijection between S_I and N. This in turn prevents this utility function from being computable, and as Peter de Blanc’s paper shows, it cannot even be bounded below by a computable function.
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 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.
I’ve just demonstrated an example in which I provided a bijection between S_I and N, and computed the sum.
A counterexample to what? Peter de Blanc defines exactly what he means by S_I. Replacing S_I by something completely different and calling that S_I does not make a counterexample to what he proves. It may be an example of something worth proving; he himself suggests this at the end of his 2009 paper:
This is supposed to be a counterexample. A counterexample means you are allowed to select any possible case. This is one possible case. I am not “replacing S_I by something completely different.” I am choosing one possible S_I. If you don’t like my choice of S_I, you need to show that it is not a possible case. That would include showing that I have chosen an S_I that is inconsistent with my earlier choices. Try to do that.
If I had specified the set of observations I, then also specified S_I in a way not determined by I, then you could make that argument. As I have not specified I, you need to show that my choice of S_I is inconsistent with any possible set I in order to make the argument you’re trying to make.
Let J be the constant set that I is currently equal to. Your agent’s set of hypotheses then does not contain the computable function f(k) =
(2(1-1/2^k))^4 for all K in J
-k for all K not in J
By construction, this hypothesis must be compatible with the known input-output pairs, since it is indistinguishable from your f_4 given the observations in J. S_I must therefore contain f iff it contains f_4. Your S_I does not satisfy this, so it is not a counterexample.
I think you’re right. You may have unravelled my counterexample. Tentative congratulations!
I now get to eat a piece of chocolate, as a reward for being proven wrong.
Suggestion: treat yourself to a second piece of chocolate and add an ETA at the top of the post—the parent comment is buried too deeply in the thread, for informational purposes.
In the original paper, S_I is determined by I. There is no I for which your set S_I is the set defined in the paper. It really is as simple as that.
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.