Hacker News Reader

Comment by rssoconnor | Hacker News Reader

It is not /really/ countable in a computable sense; it is undecidable whether or not a program generates a real number or diverges (as a consequence of Rice's theorem). Thus you cannot compute a function that enumerates all programs that compute real numbers.

View on HN

I'm not sure what you mean exactly by "countable in a computable sense." Sure, certainly you can't generate one program that enumerates all the programs that compute real numbers.

But the set of programs that compute real numbers is a subset of all programs, and the set of all programs is countable. Therefore the set of computable numbers is countable.

edit: I think maybe it wasn't clear that I'm talking about cardinality and measure? To be a little clearer - I'm saying that the computable numbers have (standard) measure 0 because they have countable cardinality. Any subset of the real numbers with countable cardinality has measure 0. And the set of all real numbers, of course, has uncountable cardinality.

I get what you are saying. My point is that someone who is philosophically disinclined to buy into the "existance" of non-computable real numbers, e.g. constructivists, because they are not effectively computable, are also going to be, by the same logic, disinclined to buy into your argument that the computable real numbers are countable, because in order to count the computable real numbers you would need a function to enumerate them, at that function is also not computable.

> But the set of programs that compute real numbers is a subset of all programs, and the set of all programs is countable. Therefore the set of computable numbers is countable.

A constructivist is also not going to buy into your argument that a subset of a countable set is countable. Heck, the constructivists are not even going to buy into an argument that a subset of a finite set is necessarily finite (they have a term for such subsets: 'subfinite').

Yes, I know that this constructivism feels so bizarre that it cannot possible be coherent; the whole notion of cardinality appears to become useless. But you get used to it after a while.

Heck, even in classical mathematics, trichotomy of cardinally requires (or rather /is/) the axiom of choice. So cardinality wasn't really super well behaved to begin with.

Reply on news.ycombinator.com