Saturday, 25 December 2010

computability theory - {transcendental numbers} {computable transcendental numbers}

Note: Answer is pending update per attached comments.



The difference, stated informally, is that that the non-computable transcendentals in their k-base digit representation are entirely random and non compressible. A computable transcendental, such as e, can be represented by a finite algorithmic description, such as a series expansion, which is a form of compression. For the non-computable numbers no such shorter representation exist. Their shortest computational description is their own infinite digit sequence.
You can read more about computational complexity here:
http://en.wikipedia.org/wiki/Kolmogorov_complexity.



There is a wealth of similar numbers to the Ω class of numbers. In general it is "easy" to come up with new definitions for such numbers. These all belong to the countably infinite set of non-computable definable numbers.



To make matters worse, what is left are the non-definable (and therefore also non-computable) numbers. They are the numbers that cannot be described in any way what-so-ever, other than by just iterating through their infinite non-compressible digit sequence. The set of all non-definable numbers is uncountable.

No comments:

Post a Comment