News for hackers. Stuff that matters.
Re:A simple proof that pi is irrational [pdf] by moomin on Sunday August 11, 2024 @04:12PM (#41219010)
Okay, here’s where I find it gets weird.

Being rational means you’re a solution to a linear equation. sqrt(2) is irrational.

Being algebraic means you you’re a solution to an algebraic equation. Pi is transcendental, which means it’s not only irrational but non-algebraic.

Being computable means you can write a terminating program to compute the nth digit of the number. Pi is computable, I have no idea what isn’t computable.

But… just as naturals are countable, so are rationals, so are algebraic numbers, so are computable numbers. Which in turn means that the non-computable numbers that I can’t even describe are the VAST majority of numbers on the real number line.

Re:A simple proof that pi is irrational [pdf] by geertj on Sunday August 11, 2024 @04:37PM (#41219163)
> I have no idea what isn’t computable.

The busy beaver function Σ(n) is not computable, at least, not for every n. If it were, it could be used to determine if an arbitrary Turing machine halts, solving the halting problem.

To get from this non-computable function to a non-computable number, you can construct the finite number R = 0.Σ(1)Σ(2)Σ(3)... that concatenates all busy beaver numbers. Its first few digits are R = 0.1621 ... (thanks to ChatGPT for this step).

Re:A simple proof that pi is irrational [pdf] by thomasahle on Sunday August 11, 2024 @08:15PM (#41220170)
I think ChatGPT got it a little wrong. For the argument to work, you need to be able to reconstruct the Σ function from R. But you don't know the boundaries of the numbers, so you can't.

However, if you include the number of digits in each number, that is

    R = 0.|Σ(1)|Σ(1) |Σ(2)|Σ(2) |Σ(3)|Σ(3)... = 0.11 14 16 213
That should work.
Re:A simple proof that pi is irrational [pdf] by geertj on Monday August 12, 2024 @02:29PM (#41227744)
I see.. You're saying that theoretically, it may be possible to compute the digits of R in a different way, without computing Σ(n). Since it's not possible to unambiguously get Σ(n) from my definition of R, you cannot use the halting problem to prove that such a computation is impossible.

In your version of R, you can unambiguously get Σ(n) from R, therefore, the halting problem proves that R itself is not computable. Nice!

Re:A simple proof that pi is irrational [pdf] by thomasahle on Tuesday August 13, 2024 @01:36PM (#41237520)
Exactly! We must show that computing R will let us compute Σ(n). Not the other way around.

Actually, my version has an issue, which is that (while you can read the Σ(n) unambiguously after reading |Σ(n)|) you can't unambiguously get the |Σ(n)| without knowing their length.

The most efficient way, I believe, is to just include ||Σ(n)|| as well, and so on recursively down until you have only one digit. But then you'll also need to keep track of the length of the sequence, so it's a mess.

Better just write everything in unary. So (1, 4, 6, 13) gets encoded as

    R = 10 11110 1111110 11111111111110 ...
After-all, we are not trying to be efficient with out digits. Just making a theoretical argument :-)
Re:A simple proof that pi is irrational [pdf] by lisper on Sunday August 11, 2024 @04:55PM (#41219252)
Re:A simple proof that pi is irrational [pdf] by hsolatges on Sunday August 11, 2024 @04:55PM (#41219253)
That is remarkable. Thanks.
Re:A simple proof that pi is irrational [pdf] by dullcrisp on Sunday August 11, 2024 @05:54PM (#41219569)
Or put more plainly, most infinite strings of digits don’t represent anything meaningful.