There's an interesting question one could ask about Gödel’s incompleteness: provability aside, is G actually true or not?
Well, G appears to be just a number; it's Gödel's encoding scheme and the associated mechanics that give it an internal meaning. That said, in the world we intended to create, we'd be tempted to say that G is semantically true: it's a complicated formula that says it can't end up on Gödel's truth pile, and it never does.
At the same time, because 🔮 can never make this determination about G, the system works independently of the semantic truth of the sentence. In other words, it's compatible both with a universe of Peano arithmetic augmented with "G = true" just as it's compatible with one constructed by saying "Peano axioms + G = false". In both cases, it can't infer the value on its own.
To clarify, when we specify the design of Peano arithmetic, we give a collection of rules for some collection of underlying objects, but we don't specify what these objects are. We just intuitively assume that the axioms perfectly select for a concrete collection of objects and object relationships (a "structure") that looks like natural numbers: there's an object representing "0", a successor we call "1", and there's nothing weird going on. In this model, G indeed ought to be semantically true.
Yet, the axioms, as expressed in the language of first-order logic, are actually loose enough that they can also be satisfied by pathological, non-standard structures that, for example, include infinite sequences of "extra" numbers unmoored from the sequence of naturals. And if PA is bootstrapped over these bizarro structures, 2 + 2 is still 4, but G can be semantically false.
The precise mechanics of these non-standard models are essentially indescribable, but they exist. If we had a formal first-order logic proof that they don't, then 🔮 could follow the same reasoning to conclude that G must be always true, and then promptly implode.
In a similar way, we can't know BB(z) because it's *independent* of the mathematical theory we're using. ZFC can be bootstrapped over various structures. Some of them match our normal understanding of sets, and some contain horrors from the deep. For the most part, ZFC works the same in all cases, but the maximum runtime for halting machines of the z size class can differ, so the theory can't pin it down.
I'm under the impression that a consequence of all this is that there are some facts about natural numbers that are just arbitrary. Proof systems like ZFC allow us to make some statements about all natural numbers without calculating them. They're the only way we have to say anything about very large numbers beyond what we could calculate by brute force. But these proof systems simply don't say enough about how very large numbers work to pin down their behavior.
So the question is, why should we care about these very large numbers, beyond anything we could calculate, even in principle? In practice, we don't want to run any program forever, so who cares if it would haul in a million years?
And I think the answer is that we don't care about that, but we do want to prove things about what a program will do for any "reasonable" input, and we want to do it without resort to brute-force testing. It's difficult to define what a "reasonable" input would be in a clean way, so we end up trying to prove things for impractically large inputs, too.
For an alternative to the "clunkiness of Turing machines", see my recent paper "The Largest Number Representable in 64 Bits" ( https://www.mdpi.com/1099-4300/28/5/494 )
Ah, thanks, appreciated, but I think it's more on me than on you - I haven't done theoretical math or CS in decades.
The rewritten version is indeed more readable, but not really grokable. I see what you're saying, but I'm not able to follow well - I'm not sure for example, whether the BB(25) for Goldbach's theorem was an example or the actual number.
However, even from afar, your equivalence of the know-ability of BB(x) with Gödel's theorem is very interesting, even as a theoretical concept. Thanks!
Ah yeah, that "for example" should have been "in particular" =) Anyway, thanks for the feedback - I do try to write for myself from before I learned about a particular concept, but it's hard to nail it.
LLMs can do a nice job spewing proofs and symbolic notation but what good are thinking machines when we can’t define our problems in ways they can reason about?
Try using the Turing machine to calculate the equivalent of a sine (over a finite field - no unit circle) in Norman Wildberger’s rational trigonometry.
Computability and number theory is an increasingly important topic it seems.
I think it's interesting that in your constrained-memory brute force solution you didn't consider a computer that can observe (and influence) the state of another, but not the other way around. This exists in the real world, but can also be thought of as an emulator or debugger.
I digress, though, as it's not what you're going for in the article :)
It does, but it requires enough resources to represent the state of that emulated machine *and then some*. Note that I'm using "state" here in a sense broader than the state register of the Turing machine: it's the totality of the mutable universe of the computer.
If you use a computer to emulate itself recursively, you don't run out of "compute", but you run out of RAM.
There's an interesting question one could ask about Gödel’s incompleteness: provability aside, is G actually true or not?
Well, G appears to be just a number; it's Gödel's encoding scheme and the associated mechanics that give it an internal meaning. That said, in the world we intended to create, we'd be tempted to say that G is semantically true: it's a complicated formula that says it can't end up on Gödel's truth pile, and it never does.
At the same time, because 🔮 can never make this determination about G, the system works independently of the semantic truth of the sentence. In other words, it's compatible both with a universe of Peano arithmetic augmented with "G = true" just as it's compatible with one constructed by saying "Peano axioms + G = false". In both cases, it can't infer the value on its own.
To clarify, when we specify the design of Peano arithmetic, we give a collection of rules for some collection of underlying objects, but we don't specify what these objects are. We just intuitively assume that the axioms perfectly select for a concrete collection of objects and object relationships (a "structure") that looks like natural numbers: there's an object representing "0", a successor we call "1", and there's nothing weird going on. In this model, G indeed ought to be semantically true.
Yet, the axioms, as expressed in the language of first-order logic, are actually loose enough that they can also be satisfied by pathological, non-standard structures that, for example, include infinite sequences of "extra" numbers unmoored from the sequence of naturals. And if PA is bootstrapped over these bizarro structures, 2 + 2 is still 4, but G can be semantically false.
The precise mechanics of these non-standard models are essentially indescribable, but they exist. If we had a formal first-order logic proof that they don't, then 🔮 could follow the same reasoning to conclude that G must be always true, and then promptly implode.
In a similar way, we can't know BB(z) because it's *independent* of the mathematical theory we're using. ZFC can be bootstrapped over various structures. Some of them match our normal understanding of sets, and some contain horrors from the deep. For the most part, ZFC works the same in all cases, but the maximum runtime for halting machines of the z size class can differ, so the theory can't pin it down.
I'm under the impression that a consequence of all this is that there are some facts about natural numbers that are just arbitrary. Proof systems like ZFC allow us to make some statements about all natural numbers without calculating them. They're the only way we have to say anything about very large numbers beyond what we could calculate by brute force. But these proof systems simply don't say enough about how very large numbers work to pin down their behavior.
So the question is, why should we care about these very large numbers, beyond anything we could calculate, even in principle? In practice, we don't want to run any program forever, so who cares if it would haul in a million years?
And I think the answer is that we don't care about that, but we do want to prove things about what a program will do for any "reasonable" input, and we want to do it without resort to brute-force testing. It's difficult to define what a "reasonable" input would be in a clean way, so we end up trying to prove things for impractically large inputs, too.
For an alternative to the "clunkiness of Turing machines", see my recent paper "The Largest Number Representable in 64 Bits" ( https://www.mdpi.com/1099-4300/28/5/494 )
Feel free to shoot this content directly into my veins.
Great article. But are you calling this a toy?
https://en.wikipedia.org/wiki/ZX81
I grew up with ZX Spectrum 48, so of course we considered ZX 81 to be a joke.
But then the Spectrum was the one with a fancy rainbow on the keyboard, so...
LOL - I coughed up good money for my 16K RAM expansion kit!
This was an excellent and clear overview. Worth reading and then coming back to read again.
me → this article → (woosh). Or at least after the "A constrained-instruction computer" part.
I revamped that section and the following one a bit, so it might be worth another shot!
Ah, thanks, appreciated, but I think it's more on me than on you - I haven't done theoretical math or CS in decades.
The rewritten version is indeed more readable, but not really grokable. I see what you're saying, but I'm not able to follow well - I'm not sure for example, whether the BB(25) for Goldbach's theorem was an example or the actual number.
However, even from afar, your equivalence of the know-ability of BB(x) with Gödel's theorem is very interesting, even as a theoretical concept. Thanks!
Ah yeah, that "for example" should have been "in particular" =) Anyway, thanks for the feedback - I do try to write for myself from before I learned about a particular concept, but it's hard to nail it.
LLMs can do a nice job spewing proofs and symbolic notation but what good are thinking machines when we can’t define our problems in ways they can reason about?
Try using the Turing machine to calculate the equivalent of a sine (over a finite field - no unit circle) in Norman Wildberger’s rational trigonometry.
Computability and number theory is an increasingly important topic it seems.
I think it's interesting that in your constrained-memory brute force solution you didn't consider a computer that can observe (and influence) the state of another, but not the other way around. This exists in the real world, but can also be thought of as an emulator or debugger.
I digress, though, as it's not what you're going for in the article :)
It does, but it requires enough resources to represent the state of that emulated machine *and then some*. Note that I'm using "state" here in a sense broader than the state register of the Turing machine: it's the totality of the mutable universe of the computer.
If you use a computer to emulate itself recursively, you don't run out of "compute", but you run out of RAM.