Comment by drewhk | Hacker News Reader

Comment by drewhk | Hacker News Reader

Parent Full thread

> The set of all possible mapping from all possible finite strings to booleans is definitely not countable.

Just to add another perspective to this, this is one of the places where classical and constructive mathematics diverge. Do those functions that are not expressible by algorithms (algorithms are countable) even exist? Of course you can define them into existence, but what does that mean?

Another food for thought is to consider if the limits imposed on computation by the Turing machine is a law of physics? Is this an actual physical limit? If so, what does that mean about the functions not expressible by algorithms? What is so exciting about programs/algorithms that they are both a well-defined mathematical object suitable for formal analysis, but they are actually machines as well, fully realizable physically and their properties physically falsifiable.

Before anyone starting to nit-pick, I just put this comment here as a conversation starter, not a precise thought-train: this is a deep rabbit whole that I think is worth to explore for everyone interested in the computational world. I am pretty sure other commenters can add more accurate details!

These are definitely thought-provoking questions and there are branches of mathematical philosophy such as constructivism and mathematical intuitionism that explore these.

Even if computation is not directly part of the laws of physics, knowing that humans and our computers are limited to things that are finite and computable might place limits on how we can appreciate how the universe works.

This is kind of a digression but if you (or others) are interested in some examples of things that are right on the edge of these questions you should check out the [busy beaver function](https://www.quantamagazine.org/amateur-mathematicians-find-f...). This tell you the maximum number of steps an n-state Turing machine can take before halting.

It is also interesting to consider, that if all transcendental numbers exist physically, then it basically means that there is an experiment that yields the Nth digit of such a number (for any N assuming unlimited physical resources to realize the experiment). If such experiment does NOT exist though, then there cannot be any relevance physically of that Nth digit (otherwise the "relevance" would materialize as an observable physical effect - an experiment!). This is something Turing machines cannot do for uncomputable numbers, like Chaitin's Omega, etc. We can yield the Nth digit of _many_ transcendental numbers (PI, e, trig functions, etc), but not all of them. It is so interesting that physics, machines and the existence of all the real numbers are so intertwined!

Of course one can also ponder, even if a mathematical object is "un-physical", can it be still useful? Like negative frequencies in fourier analysis, non-real solutions to differential equations, etc. Under what conditions can "un-physical" numbers be still useful? How does this relate to physical observation?

And just for the fun of it: when you execute unit tests, you are actually performing physical experiments, trying to falsify your "theory" (program) :D

Reply on news.ycombinator.com