Incompleteness of Computable Numbers

1. Jun 6, 2009

Dragonfall

Can someone prove to me why computable numbers are not closed under the taking of suprema?

2. Jun 6, 2009

Dragonfall

They are everywhere dense and countable, is that enough? I think that's enough.

3. Jun 6, 2009

CRGreathouse

That's enough. I mean, Q + closure under suprema = R, so a countable superset of Q doesn't have the supremum property.

4. Jun 6, 2009

Dragonfall

True enough, thanks!

5. Jun 7, 2009

Hurkyl

Staff Emeritus
An interesting follow-up question is if the computable numbers are closed under taking the suprema of computable sets....

Alas, I believe the properties of computable real analysis is extraordinarily sensitive to the specific definitions you use for various notions. (definitions that would be equivalent in ordinary analysis frequently turn out to be inequivalent in computable analysis)

For comparison, any real closed field is closed under taking suprema of semi-algebraic sets, which are exactly those subclasses which can be defined using first-order logic and the ordered field operations.

6. Jun 7, 2009

Dragonfall

As far as I know "computable sets" are subsets of integers. What's your definition of a computable set of reals?

7. Jun 7, 2009

Hurkyl

Staff Emeritus
I don't know what the right definitions to consider are. The first two I can think of are:

(1) A Turing machine that enumerates a list of Turing machines, each of which computes a real number

(2) A Turing machine that accepts (somehow) a real number as input, and either accepts it or rejects it (or infinite loops).

8. Jun 7, 2009

CRGreathouse

(1) would be sensible. Another possible definition would be by Dedekind cuts based on ratios of definable sequences.

(2) seems to have serious problems (how to input a real number? how to operate on it in a finite amount of time?).

9. Jun 7, 2009

Hurkyl

Staff Emeritus
Sorry, I left the adjective "computable" implicit.

(And there's not necessarily any problem with an algorithm that doesn't terminate...)

10. Jun 7, 2009

Dragonfall

I think CRGreathouse means that it is not possible to recognize a real number with a TM, which can only regonize finitely many symbols, and strings of finite length.

11. Jun 7, 2009

CRGreathouse

Isn't that circular?

12. Jun 8, 2009

Dragonfall

(1) needs to be stronger. The TM must list those that are in the set, and those that aren't (say, in alternating order). It's the "recursive" vs. "recursively enumerable" thing all over again.

13. Jun 8, 2009

Dragonfall

And it's possible for (2) to use an oracle which recognize real numbers then translate them into a finite string for the TM to consider. But that bumps your model into a higher place in the arithmetic hierarchy, I think.

14. Jun 8, 2009

Hurkyl

Staff Emeritus
But we're not talking about "recognizing a real number". We're talking about "doing a calculation with a computable real number". To be computable presupposes we have a way to write the number a finite string of symbols, and the TM would be programmed to operate on such representations.

The only reason I put "somehow" in a parenthetical is because we haven't fixed a particular definition and representation.

It could be stronger, but it doesn't need to be; it's a definition, and it has properties. It may be useful for some purpose, or it might not.

15. Jun 8, 2009

Dragonfall

Ok let me elaborate:

Say a bounded set S of reals is "computable", so there is a TM alternatively enumerating TMs which compute reals that are in the set, and those who aren't. Let's say L is a stack of the former, and R a stack of the latter.

Pop L, Pop R, compute the decimal expansion until they differ. repeat until you find one in R that is larger than that of L. A<-TM from L, B<-TM from R.

Pop L, and compare until you find an TM M which compute a number between A and B. A<-M.

Pop R, and do the same thing. B<-R.

Compute the difference between A and B, this will tell you if the first k digits of A are equal to those of the supremum.

Repeat the last 3 steps until desired number of digits are computed.

Note that computable sets of reals are countable, obviously, and there are only countably many of them.

Note 2: If you want "computable set of reals" to be completely analogous to "computable set of integers", then you'd need the stronger version of your definition (1)

Last edited: Jun 8, 2009