Hacker News Reader

Comment by markusde | Hacker News Reader

> describe 0% of the rational numbers between 0 and 1

I think you mean irrational :)

What you were probably thinking of is that 0% of the irrational numbers between 0 and 1 can be described by language as single entities. Or phrased differently: If you had a magic machine that could pick a random real number between 0 and 1, with 100% probability you would get a number that no finite phrase / definition / program / book could define. That is because everything we can abstractly define is part of a countable set and the set of irrational number (and real numbers) is uncountable.

For that reason, quite a few mathematicians view the real numbers as a useful, but ultimately absurd set. Much more sane is the set of computable numbers, that is the set of numbers for which you can find an algorithm that computes the number to arbitrary precision. (More formal: A number x is computable if there exists a Turing machine that gets as input a natural number n, terminates on all inputs, and outputs a rational number y such that |x-y|<10^-n .) Every number you ever thought of is computable, but as a mathematician, working with the set of computable numbers is much more tedious than working with real numbers.

What about numbers computable with random draws? Doesnt that create the chance of hitting something totally irrational among the reals? Or how is computable numbers defined to avoid this?

> Much more sane is the set of computable numbers, that is the set of numbers for which you can find an algorithm that computes the number to arbitrary precision.

But perhaps still not as sane as one may hope. It would be very sane to be able to compute, for any two numbers, which one is larger (or whether they're equal), but sadly this is not computable for the computable numbers.

> Every number you ever thought of is computable, but as a mathematician, working with the set of computable numbers is much more tedious than working with real numbers.

I mean, I've thought of noncomputable reals like Chaitin constants.

> It would be very sane to be able to compute, for any two numbers, which one is > larger (or whether they're equal), but sadly this is not computable for the > computable numbers.

I'd like to understand - Can you explain this? It seems like it would be easy to have a Turing machines that uses the other two Turing machines, adding one digit at a time until it finds a difference.

> I mean, I've thought of noncomputable reals like Chaitin constants.

Heh, but how many digits can you actually provide? Not too many. So have you really thought of the number in any meaningful sense when you barely know any of its digits?

Also interesting that computer languages themselves are countable, so while it's hard to specify the digits algorithmically for the Chaitin constant of any computer language, you already know that the set of ALL Chaitin constants are countable.

>I'd like to understand - Can you explain this? It seems like it would be easy to have a Turing machines that uses the other two Turing machines, adding one digit at a time until it finds a difference.

I assume it runs into problems when you try to check if 2 > 2.

It's very funny how that's a really good example and made it click instantly. Thank you.

> Heh, but how many digits can you actually provide? Not too many. So have you really thought of the number in any meaningful sense when you barely know any of its digits?

I’ve never thought through very many digits of pi either. Or even 1/3 for that matter!

No, the statement holds perfectly fine for the rationals.

The basis for this statement holds, but what the statement implies does not.

That is, the numbers are a subset of the rationals, but it does not follow that we can't describe a rational with a number. In fact the rationals between [0, 1) have a well known numbering,

    [ 0/1, 1/2, 1/3, 2/3, 1/4, 3/4, 1/5, 2/5, 3/5, 4/5, 
      1/6, 5/6, 1/7, 2/7, 3/7, 4/7, 5/7, 6/7, 1/8, 3/8, ... ]

where one increments the denominator and then goes through all numerators but keeps only numerators which have GCD 1 with the denominator (since if they share a factor they were already listed).

There is a 1-to-1 mapping between integers and rationals.

Reply on news.ycombinator.com