I wonder if this is a correct argument.
A function string -> boolean is always expressible? Simply because the set of all possible mappings from all possible finite strings to booleans is countable.
It's better to say that some functions like "does this program halt?" simply don't exist.
`S = {str -> bool}` is actually uncountable. `S` is isomorphic to the power set (set of all subsets) of `str`, and `2^str` is at least as big as the set of real numbers, as any real number (like π) can be mapped to the set of string prefixes (like `{"3", "3.1", "3.14", ...}`). Since the reals are uncountable, so is `2^str` and `S`.
> `S` is isomorphic to the power set
D'oh. I missed that.
> It's better to say that some functions like "does this program halt?" simply don't exist.
Let f : (p: String) -> Boolean equal the function that returns True if p is a halting program, and False otherwise
This is really just the constructive/classical argument but I want to be specific.
You just named a function and specified a property you want it to have. However no function with this property meaningfully exists. We can manipulate the symbol just fine, but we can never look inside it because it’s not real. Classical mathematics was developed before computation was relevant and the question of decidability arose fairly late, it makes more sense to consider it an early attempt at what is now called intuitionistic mathematics. The halting problem disproved excluded middle.
> The halting problem disproved excluded middle.
That's a weird category error.
I think you are experiencing the same confusion I felt when I first started thinking about the difference between a program and a function.
The set of all possible mapping from all possible finite strings to booleans is definitely *not* countable.
What I (and the article) mean by a "function" `f : string -> boolean` here is any arbitrary assignment of a single boolean value to every possible string. Let's consider two examples:
1. Some "expressible" function like "f(s) returns True if the length of s is odd, and returns False otherwise".
2. Some "random" function where some magical process has listed out every possible string and then, for each string, flipped a coin and assigned that string True if the coin came up heads, and False if it came up tails and wrote down all the results in a infinite table and called that the function f.
The first type of "expressible" function is the type that we most commonly encounter and that we can implement as programs (i.e., a list of finitely many instructions to go from string to boolean).
Nearly all of the second type of function -- the "random" ones -- cannot be expressible using a program. The only way to capture the function's behavior is to write down the infinite look-up table that assigns each string a boolean value.
Now you are probably asking, "How do you know that the infinite tables cannot be expressed using some program?" and the answer is because there are too many possible infinite tables.
To give you an intuition for this, consider all the way we can assign boolean values to the strings "a", "b", and "c": there are 2^3 = 8. For any finite set X of n strings there will be 2^n possible tables that assign a boolean value to each string in X. The critical thing here is that 2^n is always strictly larger than n for all n >= 1.
This fact that there are more tables mapping strings to boolean than strings still holds even when there are infinitely many strings. What exactly we mean by "more" here is what Cantor and others developed. They said that a set A has more things than a set B if you consider all possible ways you can pair a thing from A with a thing from B there will always be things in A that are left over (i.e., not paired with anything from B).
Cantor's diagonalization argument applied here is the following: let S be the set of all finite strings and F be the set of all functions/tables that assigns a boolean to each element in S (this is sometimes written F = 2^S). Now suppose F was countable. By definition, that would mean that there is a pairing that assigns each natural number to exactly one function from F with none left over. The set S of finite strings is also countable so there is also a pairing from natural numbers to all elements of S. This means we can pair each element of S with exactly one element of F by looking up the natural number n assigned to s \in S and pairing s with the element f \in F that was also assigned to n. Crucially, what assuming the countability of F means is that if you give me a string s then there is always single f_s that is paired with s. Conversely, if you give me an f \in F there must be exactly one string s_f that is paired with that f.
We are going to construct a new function f' that is not in F. The way we do this is by defining f'(s) = not f_s(s). That is, f'(s) takes the input string s, looks up the function f_s that is paired with s, calculates the value of f_s(s) then flips its output.
Now we can argue that f' cannot be in F since it is different to every other function in F. Why? Well, suppose f' was actually some f \in F then since F is countable we know it must have some paired string s, that is, f' = f_s for some string s. Now if we look at the value of f'(s) it must be the same as f_s(s) since f' = f_s. But also f'(s) = not f_s(s) by the way we defined f' so we get that f_s(s) = not f_s(s) which is a contradiction. Therefore f' cannot be in F and thus our premise that F was countable must be wrong.
Another way to see this is that, by construction, f' is different to every other function f in F, specifically on the input value s that is paired with f.
Thus, the set F of all functions from strings to boolean must be uncountable.
> 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
I appreciate your lengthy explanation and I largely agree with it, even though it probably doesn't help much because anybody who has not understood this yet will have stopped reading latest at 20% in. That's not your fault but just based on the observation that attention spans are short and people strongly prefer to spend their time on reading things they are interested in. And anybody interested in this subject who has this much time to spare has likely already done that elsewhere. But I'd be happy to be wrong and would welcome if just a single person gained better understanding through your text.
What I would suggest though is to avoid using the term "random" for this. I know you put it in quotes, but that term is so over-misused that we do it a disservice by adding more misuse. Numbers (or other objects) are not random, it's the process that produced them in some context that's random. Random processes have very specific, mathematically well-defined properties, just like the concept of decidability has, and throwing around the term with other meanings really does it a disservice, similar to doing the same for decidability.
What you are probably looking for is a term like "arbitrary".
Sure, “arbitrary” is a suitable term here too. A random process is just one way to generate an arbitrary function.
My use of “random” here was referring to the coin flipping process and was more for building intuition than precisely specifying all the other non-expressible functions. I was trying to allude to the fact that these other type of functions don’t have any easily expressible process behind them. When I’ve taught this stuff in the past I’ve found that people latch onto coin flipping more easily that imagining some arbitrary assignment of values.
For what it’s worth, I used to be a researcher in probability and information theory and have published papers on those topics so I am aware of the various technical definitions of randomness (Kolmogorov axioms, algorithmic probability theory, etc.)
I think you’re right about my comment being a little too lengthy for most people to find useful. I started explaining this stuff and got carried away.