What Is Computable?

### New Book Reviews!

 What Is Computable?
Written by Mike James
Monday, 08 April 2013
Article Index
What Is Computable?
NP and Non-Computable Problems
Non-Computable Numbers and Chaos

## Non-computable numbers

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

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!

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.

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.

## 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.
• 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.

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.

#### Related Articles

Non-computable numbers

Confronting the unprovable

What is a Turing Machine?

Looking at Chaos

The Programmer's Guide To The Transfinite

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

Kolmogorov Complexity

 Information TheorySo you know what a bit is – or do you? How much information does a bit carry? What is this "information" stuff anyway? The answers are, unsurprisingly, all contained in the subject called Informatio [ ... ] + Full Article The Mod FunctionWhat has modular arithmetic got to do with the real world? The answer any experienced programmer should give you is "a lot". Not only is it the basis for many an algorithm, it is part of the hardware. [ ... ] + Full Article Other Articles

<ASIN:0321117840>

<ASIN:0486614719>

<ASIN:0470229055>

<ASIN:0198250800>

Last Updated ( Tuesday, 03 September 2013 )