A number that can't be calculated
amolas.dev
amolas.dev
There is a whole field of mathematics striving to see how far you can go, analysis-wise, with just computable numbers.[0]
"A notable result is that integration (in the sense of the Riemann integral) is computable. This might be considered surprising as an integral is (loosely speaking) an infinite sum. While this result could be explained by the fact that every computable function from {[0,1]} to R is uniformly continuous, the notable thing is that the modulus of continuity can always be computed without being explicitly given. A similarly surprising fact is that differentiation of complex functions is also computable, while the same result is false for real functions."
Are real functions not a subset of complex functions? Oh, if you redirect the output to R it gets harder, just like with finding zero roots.
Starting off on a set theoretic foot, what even is a function f:A->B? Well, it's a set of pairs (a, b) with a in A, b in B, such that (a, b) in f and (a', b) in f implies a = a'. In this sense, you could say a function r:R->R is a subset of some c:C->C by defining r = {(x, x') in c : x in R}
On the other hand, the set of functions C->C is a different beast entirely, because that consists of all functions whose domain is C, whereas the set of functions R->R is all functions whose domain is R. While each individual function in R->R is a subset of some function in C->C, R->R itself is not a subset of C->C.
I'm no analyst, complex or real, but my intuition is that C simultaneously has more wiggle room in the topological sense (you have a whole extra dimension) but less wiggle room in an algebraic sense (deg n polynomials are guaranteed to have n roots in C), it's pretty easy to just stumble upon surprising and unintuitive results.
Thinking back to my grad school complex analysis course, limits are fundamentally different in C. In R, you have two directions from which you can approach a point, but in C, any sequence converging on the point is a valid perspective from which the limit must make sense. You can approach the point from a straight line in any direction, or a squiggly line, or a spiral, etc etc. So this extra dimension of wiggle room puts a hell of a strong condition on what functions can even be differentiable in the first place, and this restriction on differentiability often translates to stronger results.
Similarly for Omega, while there's no algorithm that can compute Omega to an arbitrary precision, that is not the same as saying that there's some upper bound on the precision that Omega can be computed. For any precision k, it's possible to compute Omega up to that precision. The issue is that whatever algorithm you devise to compute Omega up to a precision of k, that algorithm will fail to compute Omega for some other precision q > k. You will need a fundamentally different algorithm for q > k, but such an algorithm does exist. You'll also need a fundamentally different algorithm for precision r > q, but that also exists... ad infinitum.
How do you do that once k is large enough that it admits Turing machines whose halting behavior is independent of our axioms?
That's not as obvious as you might think. The value of BB(800) is independent of ZFC. So it isn't "just a number" if you're working in ZFC.
This is fascinating to me, because Turing machines can in principle be manifested as physical objects. It feels like you shouldn’t need axioms if you have the thing sitting in front of you, but on the other hand how else are you supposed to prove something doesn’t halt?
Still, if you have two axiomatic systems that disagree, what does that mean? Surely you can just run the machine in question for a certain number of steps to determine which system is right.
but wouldn't this be equivalent to solve the Halting Problem?
1) For all Turing Machines A, there exists a Turing Machine M such M can compute whether A halts.
2) There exists a Turing Machine M such that for all Turing Machines A, M can compute whether A halts.
Statement 1 is true, statement 2 is false.
You can apply a similar reasoning to BB(n) or your notion of Omega. For any particular choice of n, there is an algorithm that can compute BB(n) and similarly for any arbitrary precision p, there is an algorithm that can compute Omega up to that precision.
None of this is to be taken that there exists an algorithm that can compute BB(n) for all n, or that there exists an algorithm that can compute Omega up to precision p for all p.
This is itself uncomputable; therefore
> Then, we could build the mapping n -> BB(n).
This mapping is not computable.
Edit as I'm rate-limited:
What I mean is, informally, the incomputability of the algorithm to select the correct algorithm to compute BB(n) is sufficient to make that mapping uncomputable.
However, that does not mean that an algorithm to compute BB(n) for a specific n does not exist. Trivially, it does; "output BB(n)". It's just very uninteresting! What you're asking for, rather, is more like "an algorithm to prove BB(n)=x", which is a closely related but distinct problem.
Wikipedia touches on this subject with an article on omega-consistent systems, which is a very closely related property:
https://en.wikipedia.org/wiki/%CE%A9-consistent_theory
And this gives a very brief description of Omega completeness:
That's not subtle at all. Any finite number or string can be computed by a program consisting of a single very long print statement.
No such algorithm exists, no such example exists because for any particular algorithm it's always possible to determine whether it halts or not (at least in principle). It might not be practical, the proof might be incredibly difficult, but math does not have any kind of intrinsic limitation that prevents us from proving whether a specific algorithm halts.
The post and it’s analysis are still interesting, but it should probably be updated else a lot of people might take away this key point into their memory as they think about computability.
In the very comment section of that blog post someone brings this issue up, and Scott himself says:
"Yes, fine, you’re right, there’s not a single “boundary between the knowable and the knowable.” What there is, is more like a concentric series of boundaries, with signs warning you that as you proceed outward you need to take on bolder and bolder axioms (which might be large-cardinal axioms and might be something else). What’s significant about going beyond ZFC is just that, by that point, you’ve clearly passed the first of those boundaries."
The only axioms you could introduce to ZFC that would not introduce an inconsistency would be one that eliminates that non-standard model of arithmetic without also eliminating the standard model of arithmetic.
https://en.wikipedia.org/wiki/Non-standard_model_of_arithmet...
None of this requires going beyond any kind of notion of computation and any value that is computed for one such extension would necessarily have to be the same value among all consistent extensions of ZFC. It's not like you could have one extension of ZFC where BB(8000) is X and another extension where BB(8000) is Y without one of those extensions being inconsistent.
There are plenty of extensions to ZFC that add new axioms for the sake of exploring niche mathematical ideas. ZFC is nice in that it's easily motivated and can serve as a well understood foundation whose proofs can be stated without reference to additional hypotheses. It also satisfies an unbelievably broad set of mathematics, but mathematicians studying set theory often extend ZFC with additional axioms such as large cardinal axioms, Neumann/Bernays/Godel (NBG) set theory is another common extension, Kelley Morse (KM) set theory. The latter two extensions are even able to prove the consistency of ZFC. As I referenced in Scott's quote, BB(8000) is almost certainly computable by adopting one of the large cardinal axioms.
This is not true.
There is a number N where BB(n) is incomputable for all n > N. This fact tie back to being able to solve the Halting Problem, in various clever ways if you knew BB(n).
The value of BB(744) depends on whether the Riemann Hypothesis is true or false. This means that it cannot be computed in general. The Riemann Hypothesis being either true or false are both consistent with ZFC. The value of BB(748) depends on the self-consistency of ZFC.
It is not. There are a few proofs, most notably the fact that you'd have to solve the halting problem to find BB(k) for an arbitrary k. But the more interesting proof is when looking at the growth of the number of states required for larger BB(k)'s. You end up with a pretty cool contradiction[1] by constructing a very special Turing machine.
[1] http://www.coopersnotes.net/docs/langmach/CHAP10%20Busy%20Be... (pg. 403)
Nothing in your source contradicts anything I've said.
It's not computable in this sense: there's no algorithm that given n returns Omega with n bits of precision, for any n. I think this qualifies as saying it cannot be computed to arbitrary precision :)
But I understand your point -- the language here is tricky.
Trying to make things clearer: Every program that does halt can be proven to halt -- simply run the program until it halts, if we assume it halts then you get its proof for free. However, if we make no assumptions a program may run forever, so we cannot know if it halts. I believe Godel's theorems also imply there must be non-halting programs for which no proof that they do not halt exists. This closes a very interesting loophole: you might, instead of just trying to run every program until it halts, to check every proof to see if it is a valid proof that a given program P does not -- if it exists, you will always find it. But because sometimes P does not halt yet no proof exists, this loophole is closed.
As others have mentioned, indeed I believe 'different algorithm for q > k, but such an algorithm does exist' does not pan out in the sense that we could prove the correctness of such algorithms, even though they do exist! :)
Another interesting angle: you can think that, even if you had an "oracle" that gives the "true" halting value (halts or does not halt), the size of a program that decides (by encoding the oracle values somehow) all halting programs up to n must grow with n. In other words, the halting values are incompressible somehow; if it were the case that the growth was bounded, then there would exist some program P that returns the true halting value of any program (false by Turing). This leads to the notion that non-computable numbers are random (or random-like), because they are fundamentally incompressible in a certain way (and you can't, on average, compress a random string).
Edit: minor corrections
(1) Would this proof be considered acceptable? (or can we devise a system that guarantees found proofs to be acceptable)
(2) Is this procedure feasible?
If anyone has literature on this topic, this is interesting! (an optimistic alternative to incompleteness)
The halting problem is unsolvable due to a contradiction, but there is a finite set of programs with given number of symbols; one or more of them share the max non infinite running time, and if you did have the oracle to answer that, you can in fact run the algorithm provided, except for how long this would take in real time.
A different take is that you can write a program that will only terminate if ZF set theory is false, which is impossible to prove using math due to Gödel's incompleteness theorems. We assume this program should run forever, but would not be able to prove it. That program provides some upper bound to the highest BB number we could ever hope to prove with certainty: 748 according to this article from a few years back.
The problem of the post is that an all knowing oracle doesn’t have this problem, and assuming the program has finite length, our being able to prove whether it halts or not does not stop there from being an answer to that question.
https://www.quantamagazine.org/the-busy-beaver-game-illumina...
I think you are correct, but the question is simply if we can compute this maximum number - without any oracles.
Then the answer will be no, since we could decide the halting problem as shown by the author.
I'm not arguing that you can't calculate BB numbers, in fact we've calculated some of them. What I'm arguing is that you can't calculate all the BB numbers, since this will mean that the Halting Problem is solvable. Using the results of your link I guess we can say that BB numbers can be computed if n<748 (or <20 according to Aaronson).
> In 2016, he and his graduate student Adam Yedidia specified a 7,910-rule Turing machine that would only halt if ZF set theory is inconsistent. This means BB(7,910) is a calculation that eludes the axioms of ZF set theory. Those axioms can’t be used to prove that BB(7,910) represents one number instead of another, which is like not being able to prove that 2 + 2 = 4 instead of 5.
OMG! A number that's so much big that can be contained in the ZF set theory.
Easiest way to construct one is to use the diagonal argument that’s used to prove, amongst other things, the halting problem.
I like to think that God has access to much better math and computational resources than we can even begin to conceive of. ;-)
Hmmm. Just because you don't know the individual terms of the sequence, it doesn't follow that you don't know their infinite sum. Here's a trivial example: take the sum `(-1)^n Σ(floor(n/2))`. The infinite sum is obviously 0, yet we can't calculate each of the terms, nor many of the partial sums.
Yes, this is not true in general. But I think it's true for the specific definition of Ω we use in the post.
Perhaps add a small edit to your article to highlight that this particular statement isn't to be taken as a mathematical proof?
The proof that the halting problem can't be computed relies on a self-reference where you query whether the program halted and then do the opposite. But- and here's the important part- when the program references itself it requires at least one more symbol to do so as it needs somewhere to store the answer. It therefore needs an infinite stack. But we have a fixed number of symbols. Or, to put it another way: if your set of symbols is bounded, then you can only call functions that use at least one fewer symbol than the calling one, which means you will eventually run out of symbols and have a base case. Doesn't that mean the halting problem doesn't apply to the busy beaver problem?
Notably the list of BB numbers in the article matches the values of S(n) in wikipedia instead of Σ(n). Also this sentence makes more sense if you replace Σ(n) with S(n)
> If after these steps the program hasn’t halted it means it’ll never halt (by the definition of the Σ(n)).
It's trivial to construct a candidate for each n, which gives a lower bound.
What would it mean for BB(n) to "not exist"? Recall that BB(n) is defined in a very concrete way: you take all the Turing machines of size n (which are easily enumerable combinatorial objects), remove ones which do not halt, then take the largest runtime of the ones that are left. Since we can always write down a Turing machine which halts immediately, we know that there's a trivial lower bound for each BB(n), and since the Turing machines are deterministic, we know that any machine that halts must do so in a fixed number of steps. With such a straightforward construction, it's hard to see how such a number could "not exist," at least not without appealing to an ontology somewhat outside of the mainstream (e.g. ultrafinitism).
> So you can remove the ones that do not halt by inspecting them one by one and developing a specific algorithm for each one that determines if it halts or not.
Is impossible. You can’t, in general, inspect Turing machines one-by-one to determine if they halt.
It's not a constructive proof, you don't need to give a process.
Trivially a non-halting program for any n exists. Also trivially there must be some non-halting program with the highest number of steps.
We can’t necessarily find that program, but there is almost by definition some non halting program with the highest number of steps
That isn't trivial. Whether a given program halts might be independent of ZFC, or of any consistent logical system you might try to use. The question of whether such a program "really" halts is one which might not have an answer. ZFC claims there must be an answer, because LEM, but why should we care what ZFC or first order logic or anything has to say on the matter, if they can't actually tell us whether it halts?
This argument doesn't quite work since Sigma(n) is the maximum number of characters printed before halting rather than the maximum finite number of steps of computation. The argument would work for the other flavor of Busy Beaver though.
If you have some resources regarding Chaitin constant I would be very happy to read them :)
[1] https://tromp.github.io/cl/Binary_lambda_calculus.html#Halti...
Thanks :)