Incompleteness of Computable Numbers

[Dragonfall]

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

 

[Dragonfall]

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

 

[CRGreathouse]

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

 

[Dragonfall]

True enough, thanks!

 

[Hurkyl]

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.

 

[Dragonfall]

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

 

[Hurkyl]

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

 

[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?).

 

[Hurkyl]

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

Sorry, I left the adjective "computable" implicit.

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

 

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

 

[CRGreathouse]

Sorry, I left the adjective "computable" implicit.

Isn't that circular?

 

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

 

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

 

[Hurkyl]

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.

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.

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

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.

 

[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)