2 ms·
Numbers that can be computed by Turing Machines are countable, so list them: c_0, c_1, c_2, etc. Take any interval [a0,b0] (with a0 and b0 computable), and cro
by ColinWright 13y ago
Numbers that can be computed by Turing Machines are countable, so list them: c_0, c_1, c_2, etc.
Take any interval [a0,b0] (with a0 and b0 computable), and cross out your computable numbers until you find one, say, c_i, in the interval (including an endpoint). Take some strict sub-interval [a1,b1] (again with computable endpoints) within [a0,b0] such that a0<a1, b1<b0, and c_i is not in [a1,b1]. Now continue crossing off computable numbers, each time taking a sub-interval with computable endpoints to exclude any that happen to be in the interval currently under consideration.
The left hand end-points, a0, a1, a2, etc, form a strictly increasing sequence of computable points. This sequence is bounded above, and so we would like there to be a least upper bound.
And yet it cannot be one of the numbers you first chose, because each has been excluded at some stage. So here we have a strictly increasing, bounded above sequence of computable numbers such that there is no limit in the computable numbers.
This proves the computable numbers are not complete, and that makes analysis really messy.
- justinpombrio 13y agoThere's two related arguments you (may) be making. One is philosophical, and to that I say: can you give an algorithm to compute a0, a1, ...? If you can't (and I suspect you can't), I'd be hesitant to say that such a sequence exists. But I don't think there's a useful argument to have here ;-). But more concretely: no, the computable numbers aren't complete. Why would this make analysis messy? I didn't find the presentation and results in Computable Analysis (the book) all that different from what you find in an ordinary analysis course. Is there something it makes hard which I'm missing? (This might be impossible to answer without specific knowledge of Computable Analysis; remember that the definitions of, e.g. limits, are different.)