Non-computable numbers

### New Book Reviews!

 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

 Introduction to Boolean LogicIt may sound like a daunting topic, but Boolean logic is very easy to explain and to understand. It represents the simplest of all the logics and the very basis of computing. Today, November 2, 2 [ ... ] + Full Article Programmer's Introduction to XMLXML is a general purpose markup language that can be used to control the structure of data. Despite the fact that many prefer the simplicity of JSON, it still has many advantages. What makes it so goo [ ... ] + Full Article Other Articles

<ASIN:1110750331>

<ASIN:186046324X>

<ASIN:0486421651>

<ASIN:1568812736>

<ASIN:1402757964>

<ASIN:1933836881>

Last Updated ( Friday, 22 January 2016 )