Non-computable numbers

A more important example is that of non-computable numbers.

The famous halting problem is interesting but it just stops you from computing something that almost seems paradoxical before you start. Who cares if it is impossible to write a program that can work out if another halts or not? This seems fairly unimportant and based on slipping in an infinity when no one is looking.

A more serious sounding problem is that there are numbers that are non-computable. That is there are numbers that you cannot write a program to print out and make visible. This seems a little more serious and might even have practical consequences.

Consider the simple fact that every program is just a string of binary digits. Now think about this string of digits as a binary number. To every program there is an integer and to every integer a program.

Even if you factor in that there are a few different types of machine and each integer corresponds to more than one program there are still only as many programs as integers – it’s the way infinity is! (See the chapter on transfinite numbers).

Now for the killer observation.

There are more real numbers, i.e. fractions and non-repeating decimals like the square root of two and pi, than there are integers. This is a bigger infinity and so the conclusion has to be that there aren’t enough programs to go around. Most of the numbers just don’t have programs that work them out. You can write a program to compute all of the digits of pi, or e or root 2 but these are the few. The majority of numbers just don’t have programs, or names for that matter, and will remain forever hidden in the continuum of the number line.

Some people find this all deeply disturbing. Some find it totally irrelevant because it doesn’t impinge on practicalities.

Who cares if pi is just a rare regularity and the rest of the numbers are inaccessible. After all if we only want to compute the area of a circle pi is the only number that matters – the rest can remain locked out! Even so it is still worrying that some things in this universe are non-computable.

You can extend the same type of thinking to ideas like information and randomness.

For example, if you have a number like pi, an infinite non-repeating sequence, and there is a program that generates it then the program is shorter than the bit sequence it generates. In this sense the information contained in pi is the same as the information contained in the program that generates it - see the Chapter on Kolmogorov Complexity

On the other hand there are other numeric sequences, in fact most numeric sequences, that don’t have programs that generate them. In this sense these number sequences are more random than pi, say.

Follow this route and you can find out a lot about randomness and information - see the Chapter on Information theory.

Chaos?

At the other extreme you can try to ignore it and say that all computations are approximate and it doesn’t matter if there are lots of sequences that cannot be generated by a program, what matters is that any sequence can be approximated by a program to any accuracy you care to mention. In this crude sense every number is computable.

You can compute anything you want to, to any accuracy you desire, and all of this nonsense about non-computability is idealistic nonsense.

Only then you have the problem of chaos to deal with, which in essence is that approximation doesn’t save you from anything.

If you believe that the universe is mechanistic then another way of saying this is that there is a program for it. Newton believed this and this is essentially his legacy in all of classical physics.

Now we have to face up to the fact that even if we were given the initial conditions of every particle in the universe we still couldn’t compute what happens next. Chaos blurs everything to the point that it becomes essentially non-computable.

Well not everything. There are some algorithms that are numerically stable. They converge to the correct answer no matter what sort of errors are included in the initial data.

These are good algorithms in a different sense to the polynomial time algorithms described earlier. They are stable and there is little more to say.

Now we come to the really difficult part. Is the universe algorithmic?

Is the universe describable by a set of rules that allow you to say what will happen next?

Quantum mechanics says a very definite no. The basic principle of quantum mechanics says, to misquote Einstein, “God really does play dice with the universe”.

This is easy to say but think about it for a moment. What we are saying is that nature, the universe, doesn’t have an algorithm that works out how a particle, an electron say, moves from point A to point B.

So how does the particle get from point A to B?

Is the universe as limited as a Turing machine and simply cannot compute the behaviour of the particle. If so it is stranger than most people can imagine and acceptance of the fact is as good as it gets.

Or is it that the Universe is the computation for the particle to get from point A to B but there is no shorter or simpler program that can compute the answer faster. In other words there can be no prediction because the actual outcome is the result of the only computation possible. 

So to sum up:

• there are difficult computations that are effectively impossible unless we can find radically better algorithms simply because of the time they take.
  
  
• there are logically impossible computations because if they were possible they result in paradoxes. These indicate the limits of logic rather than practice because there is usually an infinity in the argument.
  
  
• There also is a simple counting argument which shows that there must be lots of things that are non-computable because there just aren't enough programs to go around.
  
  
• Even if you allow for approximate computing and getting an answer that is as close as you like there are problems with computation diverging rapidly from reality.

and finally

• There are some things that can be computed by algorithms that are more compact than they are but there are computations that are not compressible in this sense. 

The study of computation and what makes is hard and what makes it a good model of the universe is not just about computers.

To quote Dijkstra

"Computer science is no more about computers than astronomy is about telescopes."

A Computable Universe - Roger Penrose On Nature As Computation    

NP-Complete - Why So Hard?       

Classic Nintendo Games Are NP Hard       

Physics Is NP Hard       

Pancake flipping is hard - NP hard       

A Programmers Guide To Theory
First Draft

There is a more recent version of this:

Now available as a paperback and ebook from Amazon.

A Programmers Guide To Theory - NP & Co-NP

Contents

1. What Is Computable?
2. Finite State Machines
3. What is a Turing Machine? 
4. Computational Complexity
5. Non-computable numbers
6. The Transfinite
7. Axiom Of Choice
8. Lambda Calculus
9. Grammar and Torture
10. Reverse Polish Notation - RPN
11. Introduction to Boolean Logic
12. Confronting The Unprovable - Gödel And All That
13. The Programmer's Guide to Fractals
14. The Programmer's Guide to Chaos*
15. Prime Numbers And Primality Testing
16. Cellular Automata - The How and Why
17. Information Theory
18. Coding Theory
19. Kolmogorov Complexity

*To be revised

Comments

Make a Comment or View Existing Comments Using Disqus

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

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.

<ASIN:0486614719>

<ASIN:0470229055>

<ASIN:0198250800>