π is the most fascinating of transcendental numbers because it has so many ways of computing its digits. What formulas can you find that give a good approximation to π? Notice that an infinite series for π gives an increasingly accurate result as you compute more terms of the series. So if you want the 56th digit of π you have to compute all the digits up to the 56th as well as the digit of interest - or do you? There is a remarkable formula - the Bailey–Borwein–Plouffe formula - which can provide the nth binary digit of π without having to compute any others. Interestingly, this is the original definition of a computable number given by Turing – there exists a program that prints the nth digit of the number after a finite time.
The digits of π cannot be random - we compute them rather than throw a dice for them - but they are pseudo random. It is generally said that if you enumerate π for long enough then you will eventually find every number you care to specify and if you use a numeric code you will eventually find any text you specify. So π contains the complete works of Shakespeare, or any other text you care to mention; the complete theory of QFT; and the theory of life the universe and everything. However, this hasn't been proved. Any number that contains any sequence if you look for long enough is called normal, and we have never proved that π is normal.
All of this is pure math, but it is also computer science because it is about information, computational complexity and more – see the next chapter.
Summary
There is a hierarchy of number types starting from the counting numbers, expanding to the integers, the rationals, the irrationals and finally the complex numbers. Each expansion is due to the need to solve valid equations in the number type that doesn’t have a solution in the number type.
The two sets are the same size if it is possible to match elements up one to one.
The size of the set of integers – the usual meaning of infinity – is aleph-zero. The rationals can be put into one to one correspondence with the integers and so there are aleph-zero rationals.
To find a set with more elements than aleph-zero you need to move to the irrationals. The irrationals cannot be enumerated and there are aleph-one of them.
The union of any sets of size aleph-zero is a set of size aleph-zero. The Cartesian product of sets of size aleph-zero is a set of size aleph-zero. It is only when you take the power set 2A do we get a set of size aleph-one.
The number of programs or equivalent Turing machines is aleph-zero. Therefore there are not enough programs to compute all of the irrationals – the majority are therefore non-computable numbers.
Similarly there are not enough formulas for all the irrationals and in this sense they are beyond the reach of mathematics.
The irrationals that are roots of polynomials are called algebraic. However, as there are only aleph-zero polynomials, most of the irrationals are not the roots of polynomials and these are called transcendental.
The majority of transcendentals are non-computable but some, including numbers like π, are not only computable, but seem to be very easy to compute.
A Programmers Guide To Theory
Now available as a paperback and ebook from Amazon.
Contents
What Is Computer Science? Part I What Is Computable?
TestSprite has announced an early access beta program for its end-to-end QA tool, along with $1.5 million pre-seed funding aimed at accelerating product development, expanding the team, and scaling op [ ... ]
