Are All Numbers Computable?

Vishnu Mangalath, The University of Western Australia

Pick a random point between zero and one. Can you write a program that computes that number to any decimal point? The answer, surprisingly, will almost always be no. This is because almost every real number is not computable, meaning there is no program that computes the number to a desired precision. This is quite an odd notion, since almost every number you will have seen, rational or irrational, will have been computable. The reason for this is because every algorithm can be simulated by a model called a Turing machine, and there are only countably many Turing machines.

A Turing machine is a very simple model of a computer developed by the mathematician and computer scientist Alan Turing. It operates on an infinite strip of tape divided into discrete cells. In each cell, there is a zero or a one, onto which the machine can read and write. This happens one at a time, and according to a set of finite instructions given by the user. It turns out that despite the simplicity of this model, every algorithm run by modern computers can be represented by a Turing machine.

Since the list of instructions must be finite we can represent every Turing machine as a finite sequence of zeroes and ones. This means there is precisely one Turing machine for each natural number, implying that the number of Turing machines is countable. The real numbers, however, are uncountable. So the vast majority of real numbers are not computable. One example of a non-computable number is Chaitin’s number, which represents the probability that a randomly constructed program will halt.

We can then extend the notion of computable numbers to computable analysis. This is concerned with extending notions from real analysis, which is the study of functions from the that map real numbers to real numbers, to the set of computable numbers. There are quite a few results from real analysis that have similar formulations in computable analysis, such as the Heine-Borel theorem.

Vishnu Mangalath was one of the recipients of a 2017/18 AMSI Vacation Research Scholarship.

Contact Us

We're not around right now. But you can send us an email and we'll get back to you, asap.

Not readable? Change text.