cobbal
Joined 16 years ago
Joined 16 years ago
As a simple example, we know that BB(1000) <= BB(1001) (since you can encode the longest running 1000-TM with an extra, unused state as a 1001-TM) even though we will never know either of those values.
The argument that it grows faster than any computable function is similar in that it proves things without knowing concrete numbers. (I'd have to look up the details of the proof to say more)
If Fermat had a book with larger margins, would Weil have devoted so much time to proving the Taniyama-Shimura conjecture? No one can say.
You can argue if it actually installs the software or just nags the user to install it, but neither are things microsoft would allow a monitor "driver" to do if they had any integrity.
The two tasks of writing code and engineering software cannot be separated without damaging the integrity of the mental model of the engineer. Having architects who didn't interact with the code always produced map/territory mismatches.
> Beginning January 2026, all ACM publications and related artifacts in the ACM Digital Library will be made open access.
The key characteristic of a compiler is that it takes a source language with a well-defined meaning to a target language with a well-defined meaning.
The reason claude fails to be a compiler is that its input language (english) can't be precisely defined. (And even if that were possible, it would very often fail to preserve the meaning when "compiling")
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.