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

I finally have an answer to "who's your favorite singer?"

My Top Tip for Helping People Get Started Programming

GPT-f

Random paper on angles

An Image is Worth 16x16 Words

Random stuff

Lossless Data Compression with Neural Networks by Fabrice Bellard

Downscaling Numerical Weather Models With GANs (My CI 2019 Paper)

Learning Differential Forms and Questions

PyTorch Lightning is worth using