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.
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.