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

Use of emphasis in speech

Generating a lot of language data with a theorem prover

"Litany Against Fear" in Present Tense

When it's time to party we will party hard

these are people who died

divine carrot

the frog

what it’s like to get nail phenolization

Why 0 to the power of 0 is 1

Lines and Points are Circles