Hacker News Reader

Comment by xyby | Hacker News Reader

    The idea that having variables which can take on an
    infinite range of real-valued values fascinates some
    people. But you can't, not really.

Well that would mean it has an infinite amount of bits in memory, right? Because to set one variable to exactly pi would mean you set it to something that usually would need an infinite amount of bits.

View on HN

Your intuition is good, but pi is a bad example. There are ways to represent specific irrational numbers such as pi, e.g. a turing machine generating all its digits. For most numbers in R that isn't possible, however. The exceptions are called computable numbers and they form a tiny (countably infinite) subset of R.

Can you link to a proof for these "computable numbers" being a countably infinite subset of R? :)

Not the comment-er, but here's a rough sketch.

Definition: A computable number is a real number x such that there exists a total computable function f:Q->Q for which, given any r>0, f(r) is within r of x.

Proof: There are only countably many total computable functions, since each can be described as a finite string of symbols from a finite alphabet. Hence only countably many computable numbers.

Charles Petzold in "Annotated Turing" gives a good explanation of this and related subjects.

No. The Kolmogorov complexity (the information required to reproduce the information, e.g. the information required for the algorithm (divide a circumference of a circle by its diameter)) of Pi isn't infinite.

Unfortunately that just shifts the problem from one of space to one of time. (There's an algorithm for calculating the hexadecimal/binary digits of pi without calculating previous digits, but AFAIK none for the decimal digits, so YMMV depending on which base you're doing it in. That's just a particular feature of pi, though so it doesn't matter for the general point.)

Spigot!

Reply on news.ycombinator.com