Computation and transcendental numbers don't seem much connected, but these are the numbers that are irrational and in principle the most difficult to compute. But there are important exceptions.

A Programmers Guide To Theory

Now available as a paperback and ebook from Amazon.

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>

As long as you understand infinity and the fact that there is more than one type of infinity then you are lead to some imediate and important conclusions about numbers - there are both not enough of them and too many.

Included in Chapter but not in this extract

• Integers and Rationals
• The Irrationals
• The Number Hierarchy
• Aleph-Zero and All That
• Unbounded Versus Infinite
• Comparing Size
• In Search of Aleph-One
• What Is Bigger Than Aleph-Zero?
• Finite But Unbounded “Irrationals”
• Enumerations
• Enumerating the Irrationals
• Aleph-One and Beyond

Not Enough Programs!

Now we come to the final knockout blow for computation and it is based on the infinities. How many programs are there? Any program is simply a sequence of bits and any sequence of bits can be read as a binary number, a binary integer to be exact. Thus, given any program, you have a binary number corresponding to it. Equally, given any binary number you can regard it as a program - it might not do anything useful, but that doesn't spoil the principle:

• Every program is an integer and every integer is a program. 

This correspondence is an example of a Gödel numbering and it is often encountered in computer science. 

This means that the set of programs is the same as the set of integers and we realize immediately that the set of programs is enumerable. All I have to do is write a for loop that counts from 1 to 2ⁿ and I have all the programs that can be stored in n bits. Even if you let this process go to infinity the number of programs is enumerable. It is infinite, but it is enumerable and so there are aleph-zero programs.

This is a very strange idea. The Gödel numbering implies that if you start generating such a numbering eventually you will reach a number that is Windows or Linux or Word or whatever program you care to name. This has, occasionally been suggested as a programming methodology, but only as a joke.

You can repeat the argument with Turing machines rather than programs. Each Turing machine can be represented as a tape to be fed into a universal Turing machine. The tape is a sequence of symbols that can be binary coded and read as a single number. We have another Gödel numbering and hence the set of Turing machines is enumerable and if we allow the tape to be finite but unbounded there are aleph-zero Turing machines. The important point is that the number of irrational numbers isn't enumerable, it is aleph-one, which means there are more irrational numbers than there are programs.

So what? Think about the task of computing each possible number. That is, imagine each number has a program that computes it and displays it. You can do it for the integers and you can do it for the rationals, but you can't do it for the irrationals and there are more irrational numbers than there are programs, so many, in fact most, irrational numbers don't have programs that compute them. We touched on this idea in Chapter 3, but now we have the benefit of knowing about the orders of infinity.

Numbers like √2, π and e clearly do have programs that compute them, so not all irrational numbers are non-computable - but the vast majority are non-computable. To express it another way:

• Most of the irrational numbers do not have programs that compute them.

What does this mean? Well, if you think about it, a program is a relatively short, regular construct and if it generates an irrational number then somehow the information in that number must be about the same as the information in the program that generates it. That is, computable numbers are regular in some complicated sense, but a non-computable number is so irregular that you can't compress its structure into a program. This leads on to the study of algorithmic information theory which is another interesting area of computer science full of strange ideas and even stranger conclusions, see Chapter 7.

Notice that you can’t get around this conclusion by somehow extending the way you count programs. You can’t, for example, say there are an aleph-zero of programs that run on computer A and another aleph-zero that run on computer B so we have more programs. This is wrong because aleph-zero plus aleph-zero programs is still just aleph-zero programs. To avoid the problem you have to invent a computer that works with real numbers as a program so that there aleph-one of them – and you can probably see the circular argument here.