Non-computable numbers
Non-computable numbers
Written by Mike James   
Saturday, 19 December 2015
Article Index
Non-computable numbers
The Irrationals
The Standard Theory

Math too

If you are now thinking that programs to compute numbers aren't that important let's take one final rephrasing of the idea.

Consider a mathematical formula.

It is composed of an enumerable set of n symbols and as such the set of all formulae is itself enumerable. Which means that there are more irrational numbers than there are mathematical formulae.

In other words, if you want to be dramatic, most of the numbers in mathematics are out of the reach of mathematics.

There are some subtle points that I have to mention to avoid the problem of you inventing "solutions" to the problem.

Surely you can write an equation like x=a where a is an irrational number and so every irrational number has its equation in this trivial sense.

The problem here is that you cannot write this equation down without writing an infinite sequence of digits - i.e. the numeric specification for a.

Mathematical formulae can't include explicit irrational numbers unless they are assigned a symbol like pi or e and these irrationals, the ones we give a symbol to are exactly the ones that have formulae that define them.

That is the computable irrational numbers are the ones we often give names to.

The same argument holds for programs.

Also notice that if you allow general irrational numbers within a program or a formula then the set of programs or formulae is no longer enumerable. What this means is that if you extend what you mean by computing to include irrational numbers within programs then the irrationals become computable. So far this idea hasn't prove particularly useful because practical computation is based on enumerable sets.

The standard theory

Now that we have arrived at these major conclusions it might be worth giving some of the more standard math.

Mathematicians say that two sets are equal in size if you can pair up items in one set with the items in the other one-to-one with none left over - they have the same cardinality and this idea works for infinite sets as well as finite ones.

All finite enumerable sets have cardinality equal to the number of elements they contain {a,b,c} has cardinality 3.

All infinite enumerable sets can be put into one-to-one correspondence and so have the same cardinality which is traditionally called Aleph Zero or enumerable infinity.


Aleph zero the size of the first or countable infinity

The set of real numbers i.e. including the irrationals isn't enumerable and is a "bigger" set than an enumerable set - it has cardinality Aleph One and is the infinity of the continuum i.e. the full number line.

There are a whole set of increasingly large infinities with cardinality Aleph Two, Three and so on..

And, yes, the set of infinities is thought to be an enumerable infinity - but I don't think anyone has proved the enumerable part  as yet.

If you want to know more look up transfinite numbers.

This is more or less the end of the story but it really is just the beginning.

Read some computer science to find out more. 

Related Articles

Confronting the unprovable


What is a Turing Machine?

Axiom Of Choice - The Programmer's Guide 

Kolmogorov Complexity

Computational Complexity    

What Is Computable?       

The Programmer's Guide To The Transfinite       


To be informed about new articles on I Programmer, install the I Programmer Toolbar, subscribe to the RSS feed, follow us on, Twitter, FacebookGoogle+ or Linkedin,  or sign up for our weekly newsletter.






or email your comment to:



What is a Turing Machine?

The Turing machine can compute anything that can be computed. It is the very definition of computation and the fundamental tool for reasoning about computers. You really need to know what it is all ab [ ... ]

What Is Computable?

Performing a computation sounds like a simple enough task and it is easy to suppose that everything is computable. In fact there are a range of different types of non-computability that we need to con [ ... ]

Other Articles








Last Updated ( Friday, 22 January 2016 )

RSS feed of all content
I Programmer - full contents
Copyright © 2018 All Rights Reserved.
Joomla! is Free Software released under the GNU/GPL License.