News for hackers. Stuff that matters.
Re:BB(10) > Graham's Number by im3w1l on Thursday October 15, 2026 @09:02AM (#50103056)
Being independent of ZF, I guess?
Re:BB(10) > Graham's Number by davrosthedalek on Thursday October 15, 2026 @10:34AM (#50104292)
I am not sure I follow? But maybe I misunderstood your quote. It seems any given TM (And for a fixed N, there are only finite many), there are only the two option: it halts, or it doesn't halt. There is no third option? Of course, the question whether you can proof that it doesn't halt, in ZF or ZFC, is a different question. (You can always proof that it halts if you know that it halts. You run it until it halts)
Re:BB(10) > Graham's Number by im3w1l on Saturday October 17, 2026 @09:43AM (#50131124)
I'm not entirely sure about what I'm unsure about, but I think I struggle to accept that there is truth beyond the axioms. Like in my mind if the axioms can't prove whether it halts or not then that's that. There is no "but actually it doesn't halt". Or at least that's where my current thinking is, I think?

I do lack a lot of knowledge about the concept of interpretation, so maybe that's where my issue is?

Re:BB(10) > Graham's Number by cobbal on Saturday October 17, 2026 @12:13PM (#50132355)
All great questions. You're dancing around the edge of model theory here and the difference between truth and provability. It's probably past what can be explained well in a comment. Nevertheless, with omissions, simplifications, and my limited knowledge:

In logic, a model is a "set" of objects and all the true facts about those objects. For example, the integers and "1+1=2,1+2=3...". If a model deals with truth, then a "theory" is a mathematical structure that deals with provability. For example, the theory of groups contains an axiom "a+0=a" that applies to any a.

We say that a model "models" a theory when everything the theory proves is true in the model. The integers are a model of a group.

But, the integers mod 2 ({0,1}) are also a model of a group, but a very different one.

So, consider the statement "1+1≠0". The theory of groups isn't powerful enough to prove or disprove this proposition. It is a false statement in the integers, but a true statement of the mod2 integers. So there is a gap between what is true in a model, and what is provable in a theory.

(Look up both godel's completeness theorem and his incompleteness theorem for more insight into this relationship)

Back to turing machines, our most popular foundations of math is a theory named ZFC. With this theory we can prove many things, but there are also many things that can't be proven or disproven. ZFC lets us prove that "BB(500) is an integer greater than 5". But it doesn't let us prove that "BB(500)=174936...35" (pretend that's a concrete number). In fact, there probably is a model of ZFC where it is true that BB(500)=174936...35, and there is also probably a model of ZFC where BB(500)=284729...86.

Axioms define what is provable, but godel showed that there will always be more true things than there are provable things (if your theory is finite-ish). Most concrete questions about the BB function will never be provable.