Confusion about computability
May. 16th, 2011 12:07 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
sniffnoy...and, CDN is down again. This is going to be a pain...
So. Some time ago I was linked to a thing about being able to exhaustively search the Cantor space 2^ℵ0 in finite time using the facts that 1. Cantor space is compact and 2. computable functions are continuous. (Or so it's claimed - it's this second claim I want to discuss here.) This seemed incredible to me and I decided before actually reading this I should figure out what the theory behind it was - after all, how do you define computability on Cantor space when it's not even countable? Anyway I forgot about this for some time but remembered about this today, and quickly figured out that if claim 2. is true, it's not in any sense that I can discern.
Here's what I know: First off, we need a way to define computability. Computability from naturals to naturals (where here naturals can be replaced by any set with a specified bijection to [an initial segment of] the naturals) we know. So we can use this sense to say when an individual element of Cantor space is computable. We also have the notion of when a real number is computable, in terms of being able to approximate it, and if we put the usual metric on Cantor space then this definition obviously coincides with the more straightforward one. Indeed, we can generalize this notion of "computable element" to any metric space with a countable dense subset which has a specified bijection with [an initial segment of] the naturals. And with this it's easy to define what it means for a function from the naturals (or etc.) *to* this space to be computable.
The problem is, what does it mean for a function *from* this space to be computable? E.g. what does it mean for a function from R to R to be computable? This certainly seems to be something people talk about. Certainly we want to be able to say, e.g., that sin(x) is computable. OK. So after a bit of looking things up on WP, and noting that this seems to match with that page I was linked to was using as its notion of computability from the Cantor space, I was concluded that what was meant was computability where you are taking as input a Turing machine specifying a computable element of the space (and outputting whatever is appropriate). Didn't see anything there about computable functions being continuous, but I did see it mentioned that, e.g., it's impossible to compute (in this sense) whether a given real number is positive or not - how do you tell whether it's 0 or just really small? So this certainly bolsters the "computable implies continuous" intuition.
(I also came to the conclusion that if our metric space equals our countable dense subset, then the two resulting notions of computability from it might not coincide - e.g. given a rational number, determining it's denominator is clearly computable if we consider rationals in bijection with naturals, but is it computable if we instead consider it as a dense subset of itself? Well, maybe, for all I know, but it's certainly not continuous.)
But here's the problem: Pick any uncomputable real number r, and consider equality testing against r. Since you know you were handed a computable number, you can always return false! So this is computable, despite being discontinuous at r! Worse yet: Consider the function which asks "is this number computable"? You can always return true, but this is nowhere continuous!
Maybe what was meant was "continuous when restricted to the subspace of computable elements"? That seems decidedly more plausible but also much weaker. And the subset of computable sequences in Cantor space would not be closed, hence not compact, hence continuity on it would not get you the nice things this guy claims.
So what's going on here? Am I using the wrong definitions? Can anyone perhaps point me to a good reference here? (OK, I admit I haven't yet done a whole lot of searching on this, I was trying to figure it out myself...)
-Harry
So. Some time ago I was linked to a thing about being able to exhaustively search the Cantor space 2^ℵ0 in finite time using the facts that 1. Cantor space is compact and 2. computable functions are continuous. (Or so it's claimed - it's this second claim I want to discuss here.) This seemed incredible to me and I decided before actually reading this I should figure out what the theory behind it was - after all, how do you define computability on Cantor space when it's not even countable? Anyway I forgot about this for some time but remembered about this today, and quickly figured out that if claim 2. is true, it's not in any sense that I can discern.
Here's what I know: First off, we need a way to define computability. Computability from naturals to naturals (where here naturals can be replaced by any set with a specified bijection to [an initial segment of] the naturals) we know. So we can use this sense to say when an individual element of Cantor space is computable. We also have the notion of when a real number is computable, in terms of being able to approximate it, and if we put the usual metric on Cantor space then this definition obviously coincides with the more straightforward one. Indeed, we can generalize this notion of "computable element" to any metric space with a countable dense subset which has a specified bijection with [an initial segment of] the naturals. And with this it's easy to define what it means for a function from the naturals (or etc.) *to* this space to be computable.
The problem is, what does it mean for a function *from* this space to be computable? E.g. what does it mean for a function from R to R to be computable? This certainly seems to be something people talk about. Certainly we want to be able to say, e.g., that sin(x) is computable. OK. So after a bit of looking things up on WP, and noting that this seems to match with that page I was linked to was using as its notion of computability from the Cantor space, I was concluded that what was meant was computability where you are taking as input a Turing machine specifying a computable element of the space (and outputting whatever is appropriate). Didn't see anything there about computable functions being continuous, but I did see it mentioned that, e.g., it's impossible to compute (in this sense) whether a given real number is positive or not - how do you tell whether it's 0 or just really small? So this certainly bolsters the "computable implies continuous" intuition.
(I also came to the conclusion that if our metric space equals our countable dense subset, then the two resulting notions of computability from it might not coincide - e.g. given a rational number, determining it's denominator is clearly computable if we consider rationals in bijection with naturals, but is it computable if we instead consider it as a dense subset of itself? Well, maybe, for all I know, but it's certainly not continuous.)
But here's the problem: Pick any uncomputable real number r, and consider equality testing against r. Since you know you were handed a computable number, you can always return false! So this is computable, despite being discontinuous at r! Worse yet: Consider the function which asks "is this number computable"? You can always return true, but this is nowhere continuous!
Maybe what was meant was "continuous when restricted to the subspace of computable elements"? That seems decidedly more plausible but also much weaker. And the subset of computable sequences in Cantor space would not be closed, hence not compact, hence continuity on it would not get you the nice things this guy claims.
So what's going on here? Am I using the wrong definitions? Can anyone perhaps point me to a good reference here? (OK, I admit I haven't yet done a whole lot of searching on this, I was trying to figure it out myself...)
-Harry
