Programmer's Guide To Theory - Transcendental Numbers
Written by Mike James
Thursday, 14 March 2024
Article Index
Programmer's Guide To Theory - Transcendental Numbers
Not Enough Formulae
π - the Special Transcendental

π 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

#### Contents

1. What Is Computer Science?
Part I What Is Computable?
2. What Is Computation?
3. The Halting Problem
4. Finite State Machines
Extract 1: Finite State Machines
5. Practical Grammar
6. Numbers, Infinity and Computation
Extract 1: Numbers
Extract 2: Aleph Zero The First Transfinite
Extract 3: In Search Of Aleph-One
Extract 4: Transcendental Numbers
7. Kolmogorov Complexity and Randomness
Extract 1:Kolmogorov Complexity
8. The Algorithm of Choice
9. Gödel’s Incompleteness Theorem
10. Lambda Calculus ***NEW!
Part II Bits, Codes and Logic
11. Information Theory
12. Coding Theory – Splitting the Bit
13. Error Correction
14. Boolean Logic
Part III Computational Complexity
15. How Hard Can It Be?
Extract 1: Where Do The Big Os Come From
16. Recursion
Extract 1: What Is Recursion
Extract 2: Why Recursion
17. NP Versus P Algorithms
Extract 1: NP & Co-NP
Extract 2: NP Complete

<ASIN:1871962439>

<ASIN:1871962587>

 Perl v5.40.0 Shows That It Is Too Resilient To Die 01/07/2024Having faced doubt, debate and insecurity, Perl is still going after all those years, alive, kicking and making releases. Business as usual. + Full Story Pg_lakehouse Makes PostgreSQL Quack08/07/2024Pg_Lakehouse from ParadeDB is an extension that turns PostgreSQL into the analytical engine of DuckDB. Why is that useful? How do you use it? + Full Story More News