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

Just because 2 things are dual, doesn't mean they're just opposites

Boolean Algebra, Arithmetic POV

discontinuous linear functions

Continuous vs Bounded

Minimal Surfaces

November 2, 2023

NTK reparametrization

Kate from Vancouver, please email me

ChatGPT Session: Emotions, Etymology, Hyperfiniteness

Some ChatGPT Sessions