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

Now available as a paperback and ebook from Amazon.

cover600

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>

To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin.

Banner


Perl v5.40.0 Shows That It Is Too Resilient To Die
01/07/2024

Having faced doubt, debate and insecurity, Perl is still going after all those years, alive, kicking and making releases. Business as usual.



Pg_lakehouse Makes PostgreSQL Quack
08/07/2024

Pg_Lakehouse from ParadeDB is an extension that turns PostgreSQL into the analytical engine of DuckDB. Why is that useful? How do you use it?


More News

kotlin book

 

Comments




or email your comment to: comments@i-programmer.info

 



Last Updated ( Thursday, 14 March 2024 )