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

e-ink reminisces

Edwin Edwards

Middle School by Bo Burnham

How to Disable Disqus Ads on your Blog

Derivation of Reservoir Sampling

Fun with Python Iterators: Linked Lists Made Easy

Notes for November 11, 2018

Underrated Vim Option: undofile and undodir

Hot Take on Solo Travel: Starve

Alan Perlis