# ShardPhoenix comments on Stupid Questions Open Thread Round 2 - Less Wrong

15 20 April 2012 07:38PM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Sort By: Best

Comment author: 22 April 2012 01:36:09AM 0 points [-]

Oh right, I forgot that real numbers could be individually non-computable in the first place.

Comment author: 22 April 2012 04:53:59AM 2 points [-]

This is true, but not, I think, the corect point to focus on.

The big obstacle is that the real numbers are uncountable. Of course, their uncountability is also why there exist uncomputable reals, but let's put that aside for now, because the computability of individual reals is not the point.

The point is that computers operate on finite strings over finite alphabets, and there are only countably many of these. In order to do anything with a computer, you must first translate it into a problem about finite strings over a finite alphabet. (And the encoding matters, too -- "compute the diameter of a graph" is not a well-specified problem, because "compute the diameter of a graph, specified as an adjacency matrix" and "compute the diameter of a graph, specified with connectivity lists" are different problems. And if of course I was implicitly assuming here the output was in binary -- if we wanted it in unary, that would again technically be a different problem.)

So the whole idea of an algorithm that operates on or outputs real numbers is nonsensical, because there are only countably many finite strings over a given finite alphabet, and so no encoding is possible. Only specified subsets of real numbers with specified encodings can go into computers.

Notice that the whole notion of the computability of a real number appears nowhere in the above. It's also a consequence of uncountability, but really not the point here.

I'm going to go into your original comment a bit more here:

If there was a computable order, you could establish a 1-1 correspondence between the natural numbers and the reals (since each real would be emitted on the nth step of the algorithm).

You seem to be under the impression that a countably infinite well-ordering must be isomorphic to omega, or at least that a computable one must be. I don't think that would make for a useful definition of a computable well-ordering. Normally we define a well-ordering to be computable if it is computable as a relation, i.e. there is an algorithm that given two elements of your set will compare them according to your well-ordering. We can then define a well-order type (ordinal) to be computable if it is the order type of some computable well-ordering. By this definition, omega+1, and basically all the countable ordinals you usually see, are computable (well, except for the ones explicitly made not to be).

Comment author: 22 April 2012 09:56:32AM *  6 points [-]

So the whole idea of an algorithm that operates on or outputs real numbers is nonsensical

You can work with programs over infinite streams in certain situations. For example, you can write a program that divides a real number by 2, taking an infinite stream as input and producing another infinite stream as output. Similarly, you can write a program that compares two unequal real numbers.

Comment author: 22 April 2012 08:32:24PM 1 point [-]

True, I forgot about that. I guess that would allow extending the notion of "computable well-ordering" to sets of size 2^aleph_0. Of course that doesn't necessarily mean any of them would actually be computable, and I expect none of them would. Well, I guess it has to be the case that none of them would, or else we ought to be able to prove "R is well-orderable" without choice, but there ought to be a simpler argument than that -- just as computable ordinals in the ordinary sense are downclosed, I would expect that these too ought to be downclosed, which would immediately imply that none of the uncountable ones are computable. Now I guess I should actually check that they are downclosed...

Comment author: 22 April 2012 08:50:56PM 0 points [-]

What does it mean to be downclosed?

Comment author: 22 April 2012 10:25:42PM 1 point [-]

I mean closed downwardly -- if one is computable, then so is any smaller one. (And so the Church-Kleene ordinal is the set of all computable ordinals.)