Non-computable numbers
Non-computable numbers
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

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

Computability 

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.

 

blog comments powered by Disqus

 

Banner


What if Babbage..?

Charles Babbage was born in the eighteenth century - the age of the Industrial Revolution. The calculating machines he invented, although  never fully realized in his lifetime, are rightly seen a [ ... ]



Dates Are Difficult

Date and times follow their own regularities, and they have nothing at all to do with binary or even simple decimal counting. First, clock and watch makers had to find ways of working with hours, minu [ ... ]


Other Articles

 

<ASIN:1110750331>

<ASIN:186046324X>

<ASIN:0486421651>

<ASIN:1568812736>

<ASIN:1402757964>

<ASIN:1933836881>



 
 

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