3 ms·
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 di
by algorias 12y ago
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.
- StandardFuture 12y agoCan you link to a proof for these "computable numbers" being a countably infinite subset of R? :)
- alexbecker 12y agoNot 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.
- avmich 12y agoCharles Petzold in "Annotated Turing" gives a good explanation of this and related subjects.