It boggles my mind that a number (an uncomputable number, granted) like BB(748) can be "independent of ZFC". It feels like a category error or something.
replies(12):
Two lenses for trying to understand this are potentially Chastain's limits on output of a lisp program being more complex than the program itself [1] or Markov's proof that you can't classify manifolds in d>= 4.
If you try the latter and need/want to figure out how the Russian school is so different this is helpful [2]
IMHO the former gives an intuition why, and the latter explains why IMHO.
In ZFC, C actually ends up implying PEM, which is why using constructionism as a form of reverse math helped it click for me .
This is because in the presence of excluded middle, every sequentially complete metric space is a complete space, and we tend to care about useful things, but for me just how huge the search space grows was hidden due to the typical (and useful) a priori assumption of PEM.
If you have a (in my view) dislike for the constrictive approach or don't want/have to invest in learning an obscure school of it, This recent paper[3] on the limits for finding a quantum theory of everything is another lens.
Yet another path is through Type 2 TMs and the Borel hierarchy, where while you can have a uncomputable number on the input tape you algorithms themselves cannot use them, while you can produce uncomputable numbers by randomly selecting and/or changing an infinite sequence.
Really it is the difference between expressability and algorithms working within what you can express.
Hopefully someone else can provide more accessible resources. I think a partial understanding of the limits of algorithms and computation will become more important in this new era.
[1] https://arxiv.org/abs/chao-dyn/9407003 [2] https://arxiv.org/abs/1804.05495 [3] https://arxiv.org/abs/2505.11773
Like, a TOE is not expected to decide all statements expressible in the theory, only to predict particular future states from past states, with as much specificity as such past states actually determine the future states. It should not be expected to answer “given a physical setup where a Turing machine has been built, is there a time at which it halts?” but rather to answer “after N seconds, what state is the machine (as part of the physical system) in?” (for any particular choice of N).
Whether a particular statement expressed in the language of the theory is provable in the theory, is not a claim about the finite-time behavior of a physical system, unless your model of physics involves like, oracle machines or something like that.
Edit: it later says: “ Chaitin’s theorem states that there exists a constant K_{ℱ_{QG}} , determined by the axioms of ℱ_{QG} , such that no statement S with Kolmogorov complexity K(S) > K_{ℱ_{QG}} can be proven within ℱ_{QG} .”
But this, unless I’m badly misinterpreting it, seems very wrong? Most formal systems of interest have infinitely many distinct theorems. Given an infinite set of strings, there is no finite universal upper bound on the Kolmogorov complexity of the strings in that set.
Maybe this was just a typo or something?
They do then mention something about the Bekenstein bound, which I haven’t considered carefully yet but seems somewhat more promising than the parts of the article that preceded it.
By the typos etc.. you. can probably also tell I was doing this on mobile, unfortunately as a passenger in a car.
To quote Chaitin’s explanation here:
> In contrast I would like to measure the power of a set of axioms and rules of inference. I would like to be able to say that if one has ten pounds of axioms and a twenty-pound theorem, then that theorem cannot be derived from those axioms.
This paper's notation does seem to be confusing, but I still think it is essentially complete with the above.
"K_{ℱ_{QG}}" would probably most commonly be L in most descriptions, a natural number that is the upper bound of complexity for provable statements in a formal system S
L is not a limit on complexity, it means that there is no formal proof for S that its Kolmogorov complexity exceeds L, for any string.
You can still prove that there are strings far more complex than L with S, and in fact there will often be far more of those strings than the ones equal to or less than L.
It is a limit on what you can prove about those strings with a greaterKolmogorov complexity in S.
Or to rewrite the above:
"There exists a natural number L such that we can't prove the Kolmogorov complexity of any specific string of bits is more than L."
Does that help or did I miss the mark on your objection?
The issue is that what they said seemingly was not
"There exists a natural number L such that we can't prove the Kolmogorov complexity of any specific string of bits is more than L."
But
"There exists a natural number L such that we can't prove (in ℱ_{QG}) any statement S whose complexity is more than L.",
which is wrong.
They later go on to say “These strings cannot be generated by programs of length <= n, and hence cannot correspond to provable statements in ℱ_{QG}.” which follows from the previous wrong statement but doesn’t follow from the accurate statement you gave, which seems to suggest that they really did mean the inaccurate statement that they wrote, not the correct one you wrote.