Uncomputability and philosophy


This post is part interesting tidbit, part random philosophizing. It assumes some familiarity with (basic) set theory and theoretical computer science.

There exist numbers that are called uncomputable, meaning no program exists that can compute them to an arbitrary number of decimals digits.

The basic reason for this is that the set of all programs is what’s called countable in mathematics, but the set of all real numbers is uncountable, meaning there are infinitely many numbers that no program can give the nth digit to.

Here’s an example of one: the infinite sum of 2\^ -BB(i) with i spanning 1 to ∞. BB(i) is the busy beaver function (look that up on Wikipedia). This sum is approximately .5156254…

While this function can be approximated, it cannot be approximated by any algorithm to as many digits as you want. If you could approximate it to arbitrary precision, you could solve the halting problem.

However, any real number can be approximated via rational numbers, which are countable. This is sort of our saving grace when it comes to practical applications (this part is the unwarranted philosophizing).

Interestingly, the set of computable numbers forms a field, meaning all arithmetic can be done with computable numbers and will only output computable numbers.

Related Posts

Handy command line benchmarking tool

Stan Rogers

Ultimate Hot Couch Guy

Quote on Java Generics

The Programmer Tendency

Figure out undocumented JSON with gron

Mental Model of Dental Hygiene

Book Review: Swastika Night

Is there a name for this construction?

Fun with negation and idioms