Comment

Comment by cobbal

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.

parent cobbal 14 days ago

No comments yet

Be the first to share your thoughts.

Live from the official Hacker News API

A modern reader for Hacker News · SvelteKit + Skeleton