47
write it in a very short form is clearly because it has an obvious pattern, i.e. all of the zeros. We can contrast this with a number such as 3476081933756308203956271 which, unless there is a fluke about the number, e.g. it happens to be the 2053 rd triangle number, can quite possibly not be specified in any shorter form than by writing it in full. This may sound all well and interesting (or not, depending on your tastes) but not the basis of a proper mathematical theory. However, Chaitin has shown that a rigorous branch of mathematics can be developed from this, which he has called Algorithmic Information Theory. As just one example of the results of the theory, Chaitin has proved that there are indeed numbers which are random in exactly his sense of the word, i.e. for which there is no quicker way to write the number than simply writing it out. The culmination of this is his definition of a number which he labels Ω, i.e. a capital Greek ‘omega’, presumably chosen due to the fact that this is the last letter of the Greek alphabet, it being the ‘most random’ number and in some sense the last thing which Mathematics can specify. Chaitin’s proof that Ω is random is not simple, but the basis of it rests on Alan Turing’s ideas of computability and the halting problem, first discussed in Turing’s 1936 paper, ‘On computable numbers, with an application to the Entscheidungsproblem’ [3]. The ‘Entscheidungsproblem’ is the question of whether a computer program could ever be written which would be able to determine whether any computer program will come to a stop in a finite amount of time.
To illustrate Turing’s argument, consider the computer program:
1. Let x = 10
2. If x = 10 then print x and stop, otherwise go back to line 1.
This clearly stops, or ‘halts’, after the second line.
Compare this to the program:
1. Let x = 10
2. If x = 15 then print x and stop, otherwise go back to line 1.
We can see that this second program will never stop.
Made with FlippingBook - Online Brochure Maker