9 ms·

I'm hoping someone can enlighten me here. My understanding is that there is a turing machine of 748 states [0], which halts iff ZFC is inconsistent (Thm 1). But

by tybug 3y ago

I'm hoping someone can enlighten me here. My understanding is that there is a turing machine of 748 states [0], which halts iff ZFC is inconsistent (Thm 1). But this machine is a "physical" object, in the sense that we can materialize it on a computer and run it. Though we don't have the computing power for this currently, there is nothing in principle stopping us from running this machine for BB(748) steps: if it halts, we have proven by Thm 1 that ZFC is inconsistent. If not, we have similarly proven that ZFC is consistent. I want to stress that this is key to my confusion. This is not just some abstract result; this is a computation that we can perform and draw a real value from. Of course, I'll now fall back on godel's second incompleteness theorem and say that one cannot prove, inside ZFC, that ZFC is consistent. But if the above turing machine halts, then we proved ZFC is consistent - a contradiction! Where is the mistake here? My current guess is there is a technical detail in the proof of Thm 1 which uses a stronger metatheory than ZFC to show that the 758-state turing machine halts iff ZFC is inconsistent. This is not a contradiction, because yes, we can run the turing machine for BB(748) steps, but that will only show that ZFC+ proves ZFC is consistent, which is already well known - ZFC + there exists an inaccessible cardinal does the job. However, I haven't looked at the paper in detail to know whether this is the case. Does anybody who has thought deeply about this problem have insight to offer? [0] https://www.ingo-blechschmidt.eu/assets/bachelor-thesis-undecidability-bb748.pdf https://www.ingo-blechschmidt.eu/assets/bachelor-thesis-unde...

Pannoniae 3y ago
The only problem is that proving it halts is "easy" - run the program, wait a few million years, it halts. Yey. Proving it doesn't halt is much harder, since you can run it for TREE(3) steps if you want, that's still not proof it won't halt in TREE(3)+1 steps. So in a way, it's not possible to "just run it", sadly.
hakuseki 3y ago
> there is nothing in principle stopping us from running this machine for BB(748) steps How would we compute the value of BB(748)?
- nine_k 3y ago
  Computing BB(748) would be best, but if we could get an upper-bound estimate that's reasonably close, that would suffice.
  - drpixie 3y ago
    Reaching a "reasonably close" upper bound estimate wouldn't provide proof ... probability maybe, but not proof.
    - dllthomas 3y ago
      If we've proved that a number is an upper bound on BB(748), then running for that many steps without halting means it has also run BB(748) steps without halting.
  - meithecatte 3y ago
    Do note that any function f(n) that is always (or even just eventually always) greater than BB(n), is uncomputable, for very similar reasons.
  - klempner 3y ago
    How can you come up with an "upper bound estimate" without having some idea of the structure of the computation of the specific 748 state Turing Machine in question? Imagine you had an oracle telling you BB(748) excluding this machine. How do you get an upper bound on the runtime of this machine? (There is an answer: this is surely not the optimal construction, and so such an oracle would give you an answer for some smaller ZFC machine which you could likely use to extrapolate a value for this machine. However, eventually you'll find a minimal state ZFC machine and that won't work anymore.)
Filligree 3y ago
So… what if BB(748) is uncomputable? Or rather, didn’t you just prove that it is?
- tybug 3y ago
  I suppose I did! I was having a hard time reconciling this with the intuition that BB(n) is in principle "computable" (colloquially speaking) for any n - my thinking went that if I want to compute BB(n), I can enumerate turing machines and run them until they halt, since infinitely looping machines are excluded from BB(n). But of course I have now reduced this to the halting problem! How do you know when you're "done" for that n? You don't. Thanks to you and sibling commenters.
  - Scarblac 3y ago
    Similarly, if you know BB(n), you can use it to solve the halting problem for Turing machines up to that size.
  - kuboble 3y ago
    Isn't the easier proof that BB(n) isn't computable something like - assume BB is computable - there exist a TM called X that computes the function - it has K states - X(K+1) produces BB(K+1) but from the definition of BB our machine cannot produce a result higher than BB(K).
    - chriswarbo 3y ago
      There's a difference between a TM/algorithm/etc. that computes a function, like BB(n) (for all Natural numbers n); versus computing a particular value, like BB(748). For comparison, there is no TM which computes the halting function halts(p) (for all programs p); but it's easy to compute particular values like halts("exit") or halts("while(true){}")
      - kuboble 3y ago
        Yes. My reasoning applies to a function n=> BB(n) Isn't that what "the function is not computable" is about? Or is the thesis that the value of BB(748) can't be computed?
Sniffnoy 3y ago
> Of course, I'll now fall back on godel's second incompleteness theorem and say that one cannot prove, inside ZFC, that ZFC is consistent. But if the above turing machine halts, then we proved ZFC is consistent - a contradiction! No, the machine halts iff ZFC is inconsistent -- as you correctly stated up top. Somewhere along the way you got this reversed, looks like. There's the problem.
- tybug 3y ago
  You're right, I misstated this - but I don't think this is fatal. The other sibling commenters pointed out the real issue with my thinking. The argument goes the same even though I misspoke here. If the machine {halts, runs forever} then ZFC is consistent. But this is a contradiction; so ZFC must be inconsistent. Tada, I have an inconsistency proof! That was the implied next step which made me think my logic was clearly incorrect (which, it was).
  - tux3 3y ago
    It's simpler than this still. If it runs forever (likely), then you will never be able to say anything about ZFC. If you see it halt, ZFC is inconsistent. If you never see it halt, you CAN'T conclude anything. But we could already do that under Gödel incompleteness, so there's nothing unusual there! If you write down random proofs on paper and find a correct proof that leads to contradiction, you've proved ZFC inconsistent, without using BB. If you keep trying forever and never find one, you'll never be able to conclude anything at any point, just like with watching the machine run
    - l33t7332273 3y ago
      > If it runs forever (likely), then you will never be able to say anything about ZFC. But if you run it for BB(754) many steps, you will know.
      - tux3 3y ago
        Yep. But I think it's easy to show that this is circular, since you can't know BB(754) without knowing whether it runs forever. And you can't prove that it'll run forever without seeing it go past BB(754) and still keep going BB(754) is X if ZFC is consistent, Y otherwise Since you can't prove that ZFC is consistent (only disprove), you can't know BB(754), which is the thing we were trying to use to determine whether ZFC is consistent in the first place! The definition doesn't make it obvious, but this is just the same as plain Gödel incompleteness, we can't get any extra info about ZFC even in principle (unless we happen to see it halt, by chance)
onetimeuse92304 3y ago
> This is not just some abstract result; this is a computation that we can perform and draw a real value from. No, this isn't a computation we can perform. There isn't enough energy in the visible Universe we can use to increase entropy to run this computation. Even if we built a computer that would use all matter and energy in the Universe, even if the computer only had one task and even if it ran the task as efficiently as is physically possible, it would not complete the computation. So this is kinda where mathematics gets disconnected from physics and reality in that we can talk and reason about those things but they no longer have physical meaning.
- thethimble 3y ago
  But if the universe is infinitely large then any finite thing should fit in it, right? Or are we saying that BB(748) can be infinite?
  - onetimeuse92304 3y ago
    Even if the universe is infinite, you can't use its infiniteness because you can't communicate partial results across infinite distances. It is natural to think that the more time you have, the further you can travel to, potentially. But when it comes to the universe, the opposite is actually true. The more time passes, the less of the universe you can reach. A lot of universe you can see today is actually not at all reachable, meaning even if you shine the light back it will never reach the destination.
    - danbruc 3y ago
      Only because our universe is currently expanding, if it wasn't or would stop in the future, given enough time you could eventually distribute the task over a large enough region to perform the computation and afterwards combine the results in one place. And one would probably have to throw in a couple of technical requirements, for example that the energy density does not decrease faster than the future light cone expands.
    - smaudet 3y ago
sligocki 3y ago
The issue is the "run the turing machine for BB(748) steps" part. We don't know what BB(748) is. If the god of busy beavers came to us and told us that value, then we could (in theory) run the TM that long and just like you say, that would prove whether ZFC is consistent. But in order for us mere mortals to compute BB(748) we would effectively need to figure out if this specific 748-state TM ever halted (along with all the other 748-state TMs).
- dllthomas 3y ago
  We don't need to know BB(748), just an upper bound on BB(748). ... which means we can't prove any upper bound on BB(748) within ZFC.
- kevinventullo 3y ago
  To put it another way, an oracle telling us an upper bound on BB(748) would be strictly more powerful than an oracle telling us ZFC is consistent.
- deepsun 3y ago
  A lot of math draws conclusions from something not possible in practice (e.g. "let's take all the natural numbers and ..."). All the parent says: if it's possible even theoretically to learn the answer to the BB problem then we've proven something that cannot be proven, as shown by Godel incompleteness.
deleted 3y ago
[deleted]
dandanua 3y ago
> if it halts, we have proven by Thm 1 that ZFC is inconsistent. If not, we have similarly proven that ZFC is consistent. The second part is wrong. We can't physically check that a program runs forever - this requires an infinite amount of time.
- modeless 3y ago
  His point is if you know the value of BB(748) then you don't have to wait forever, just BB(748) steps, as after that the Turing machine is guaranteed not to halt. The problem with his argument is that we don't know the value of BB(748). Not only that, it is incomputable, which resolves the contradiction.
  - dandanua 3y ago
    Right, we don't know the value BB(748), and moreover, "knowing" it is not enough, we would still need a proof that a certain number matches BB(748). And such a proof is not easier than a direct proof of ZFC consistency, I presume. BTW, a value can't be uncomputable, only a function can.
  - Kranar 3y ago
    It is categorically false that BB(748) is not computable. On the contrary any particular BB(n) can be computed by some Turing Machine even though there is no Turing Machine that can compute BB(n) for every n.
    - modeless 3y ago
      So then what's stopping you from running the BB(748) machine, getting the number, then running the ZFC machine and proving ZFC consistent or not?
      - Kranar 3y ago
        A proof of existence is not the same as a construction, so the fact that we know that there exists a TM that computes BB(748) does not mean that we know which specific TM does it or how to construct such a TM.
generic92034 3y ago
It is funny to me that you are going for BB(748) in this context when you could go for the much, much, ... lower number BB(745), as outlined in [0]. [0]: https://www.ingo-blechschmidt.eu/assets/bachelor-thesis-undecidability-bb748.pdf https://www.ingo-blechschmidt.eu/assets/bachelor-thesis-unde...
concordDance 3y ago
> Though we don't have the computing power for this currently I don't think you get how big BB748 is. To use a metaphor: If you took stuffed the entire observable universe full of computronium that can do more calculations in a fragment the size of a human cell than our entire civilization, then shrank that universe down to the size of a grain of sand and filled our entire universe with that, THEN did this once for every possible distinguishable person (ie. If you can say after a lifetime of detailed observation that person A isn't identical to person B then they're distinguishable) you still aren't even close to BB748. In fact, I'd be surprised if you're over BB10 and you're definitely under BB20.
- reaperman 3y ago
  BB(6) might be too large even to store (let alone compute) using all the mass and energy of the universe. I think the computable limit if you converted all the mass in the observable universe to energy (E = mc^2) would be BB(5), assuming adherence to the Laundauer Limit[0]. After calculating this I found a quote in wikipedia[1]: "There is not enough computational capacity in the known part of the universe to have performed even S(6) operations directly." That cited this paper[2], which is probably better than my model at utilizing the total available physics of the universe for calculation purposes. Anyways, the mass of the known universe is on the order of 10^56 grams[3]. Converting this all to energy using E=mc^2 yields on the order of 10^70 Joules (10^88 electron volts). Setting or clearing a single bit of information requires at minimum 0.018 eV. That allows about 10^90 bits. BB(6) may require on the order of 10^90^2 bit flips. So it is absolutely not computable using all the mass and energy in the universe. In fact, I don't think it's even storable using all the mass and energy in the universe. I don't really understand Busy Beaver, so if I got any of this wrong please correct me for the record. 0: https://en.wikipedia.org/wiki/Landauer%27s_principle https://en.wikipedia.org/wiki/Landauer%27s_principle 1: https://en.wikipedia.org/wiki/Busy_beaver https://en.wikipedia.org/wiki/Busy_beaver 2: https://arxiv.org/pdf/quant-ph/0110141.pdf https://arxiv.org/pdf/quant-ph/0110141.pdf 3: https://www.wolframalpha.com/input?i=mass+of+the+universe https://www.wolframalpha.com/input?i=mass+of+the+universe
contravariant 3y ago
A Turing machine which halts iff ZFC is consistent seems like it would be more interesting. In theory it would be possible to run it and show ZFC to be consistent that way. Although I imagine it suffers from the problem that it can only be shown to work within ZFC or any theory powerful enough to prove the consistency of ZFC, which tells us nothing.
martincmartin 3y ago
It's easy to generate all proofs in any system, just pick any axiom, then apply any inference rule, and repeat. So if you ever generate both P and not P, then you've proven its inconsistent. So if it's inconsistent, it's straight forward to prove. It's only if it's consistent that we can't prove it in any finite time.

by tybug 3y ago

Pannoniae 3y ago

The only problem is that proving it halts is "easy" - run the program, wait a few million years, it halts. Yey. Proving it doesn't halt is much harder, since you can run it for TREE(3) steps if you want, that's still not proof it won't halt in TREE(3)+1 steps. So in a way, it's not possible to "just run it", sadly.

hakuseki 3y ago

> there is nothing in principle stopping us from running this machine for BB(748) steps How would we compute the value of BB(748)?

nine_k 3y ago
Computing BB(748) would be best, but if we could get an upper-bound estimate that's reasonably close, that would suffice.
- drpixie 3y ago
  Reaching a "reasonably close" upper bound estimate wouldn't provide proof ... probability maybe, but not proof.
  - dllthomas 3y ago
    If we've proved that a number is an upper bound on BB(748), then running for that many steps without halting means it has also run BB(748) steps without halting.
- meithecatte 3y ago
  Do note that any function f(n) that is always (or even just eventually always) greater than BB(n), is uncomputable, for very similar reasons.
- klempner 3y ago
  How can you come up with an "upper bound estimate" without having some idea of the structure of the computation of the specific 748 state Turing Machine in question? Imagine you had an oracle telling you BB(748) excluding this machine. How do you get an upper bound on the runtime of this machine? (There is an answer: this is surely not the optimal construction, and so such an oracle would give you an answer for some smaller ZFC machine which you could likely use to extrapolate a value for this machine. However, eventually you'll find a minimal state ZFC machine and that won't work anymore.)

Filligree 3y ago

So… what if BB(748) is uncomputable? Or rather, didn’t you just prove that it is?

tybug 3y ago
I suppose I did! I was having a hard time reconciling this with the intuition that BB(n) is in principle "computable" (colloquially speaking) for any n - my thinking went that if I want to compute BB(n), I can enumerate turing machines and run them until they halt, since infinitely looping machines are excluded from BB(n). But of course I have now reduced this to the halting problem! How do you know when you're "done" for that n? You don't. Thanks to you and sibling commenters.
- Scarblac 3y ago
  Similarly, if you know BB(n), you can use it to solve the halting problem for Turing machines up to that size.
- kuboble 3y ago
  Isn't the easier proof that BB(n) isn't computable something like - assume BB is computable - there exist a TM called X that computes the function - it has K states - X(K+1) produces BB(K+1) but from the definition of BB our machine cannot produce a result higher than BB(K).
  - chriswarbo 3y ago
    There's a difference between a TM/algorithm/etc. that computes a function, like BB(n) (for all Natural numbers n); versus computing a particular value, like BB(748). For comparison, there is no TM which computes the halting function halts(p) (for all programs p); but it's easy to compute particular values like halts("exit") or halts("while(true){}")
    - kuboble 3y ago
      Yes. My reasoning applies to a function n=> BB(n) Isn't that what "the function is not computable" is about? Or is the thesis that the value of BB(748) can't be computed?

Sniffnoy 3y ago

> Of course, I'll now fall back on godel's second incompleteness theorem and say that one cannot prove, inside ZFC, that ZFC is consistent. But if the above turing machine halts, then we proved ZFC is consistent - a contradiction! No, the machine halts iff ZFC is inconsistent -- as you correctly stated up top. Somewhere along the way you got this reversed, looks like. There's the problem.

tybug 3y ago
You're right, I misstated this - but I don't think this is fatal. The other sibling commenters pointed out the real issue with my thinking. The argument goes the same even though I misspoke here. If the machine {halts, runs forever} then ZFC is consistent. But this is a contradiction; so ZFC must be inconsistent. Tada, I have an inconsistency proof! That was the implied next step which made me think my logic was clearly incorrect (which, it was).
- tux3 3y ago
  It's simpler than this still. If it runs forever (likely), then you will never be able to say anything about ZFC. If you see it halt, ZFC is inconsistent. If you never see it halt, you CAN'T conclude anything. But we could already do that under Gödel incompleteness, so there's nothing unusual there! If you write down random proofs on paper and find a correct proof that leads to contradiction, you've proved ZFC inconsistent, without using BB. If you keep trying forever and never find one, you'll never be able to conclude anything at any point, just like with watching the machine run
  - l33t7332273 3y ago
    > If it runs forever (likely), then you will never be able to say anything about ZFC. But if you run it for BB(754) many steps, you will know.
    - tux3 3y ago
      Yep. But I think it's easy to show that this is circular, since you can't know BB(754) without knowing whether it runs forever. And you can't prove that it'll run forever without seeing it go past BB(754) and still keep going BB(754) is X if ZFC is consistent, Y otherwise Since you can't prove that ZFC is consistent (only disprove), you can't know BB(754), which is the thing we were trying to use to determine whether ZFC is consistent in the first place! The definition doesn't make it obvious, but this is just the same as plain Gödel incompleteness, we can't get any extra info about ZFC even in principle (unless we happen to see it halt, by chance)

onetimeuse92304 3y ago

> This is not just some abstract result; this is a computation that we can perform and draw a real value from. No, this isn't a computation we can perform. There isn't enough energy in the visible Universe we can use to increase entropy to run this computation. Even if we built a computer that would use all matter and energy in the Universe, even if the computer only had one task and even if it ran the task as efficiently as is physically possible, it would not complete the computation. So this is kinda where mathematics gets disconnected from physics and reality in that we can talk and reason about those things but they no longer have physical meaning.

thethimble 3y ago
But if the universe is infinitely large then any finite thing should fit in it, right? Or are we saying that BB(748) can be infinite?
- onetimeuse92304 3y ago
  Even if the universe is infinite, you can't use its infiniteness because you can't communicate partial results across infinite distances. It is natural to think that the more time you have, the further you can travel to, potentially. But when it comes to the universe, the opposite is actually true. The more time passes, the less of the universe you can reach. A lot of universe you can see today is actually not at all reachable, meaning even if you shine the light back it will never reach the destination.
  - danbruc 3y ago
    Only because our universe is currently expanding, if it wasn't or would stop in the future, given enough time you could eventually distribute the task over a large enough region to perform the computation and afterwards combine the results in one place. And one would probably have to throw in a couple of technical requirements, for example that the energy density does not decrease faster than the future light cone expands.
  - smaudet 3y ago

sligocki 3y ago

The issue is the "run the turing machine for BB(748) steps" part. We don't know what BB(748) is. If the god of busy beavers came to us and told us that value, then we could (in theory) run the TM that long and just like you say, that would prove whether ZFC is consistent. But in order for us mere mortals to compute BB(748) we would effectively need to figure out if this specific 748-state TM ever halted (along with all the other 748-state TMs).

dllthomas 3y ago
We don't need to know BB(748), just an upper bound on BB(748). ... which means we can't prove any upper bound on BB(748) within ZFC.
kevinventullo 3y ago
To put it another way, an oracle telling us an upper bound on BB(748) would be strictly more powerful than an oracle telling us ZFC is consistent.
deepsun 3y ago
A lot of math draws conclusions from something not possible in practice (e.g. "let's take all the natural numbers and ..."). All the parent says: if it's possible even theoretically to learn the answer to the BB problem then we've proven something that cannot be proven, as shown by Godel incompleteness.

deleted 3y ago

[deleted]

dandanua 3y ago

> if it halts, we have proven by Thm 1 that ZFC is inconsistent. If not, we have similarly proven that ZFC is consistent. The second part is wrong. We can't physically check that a program runs forever - this requires an infinite amount of time.

modeless 3y ago
His point is if you know the value of BB(748) then you don't have to wait forever, just BB(748) steps, as after that the Turing machine is guaranteed not to halt. The problem with his argument is that we don't know the value of BB(748). Not only that, it is incomputable, which resolves the contradiction.
- dandanua 3y ago
  Right, we don't know the value BB(748), and moreover, "knowing" it is not enough, we would still need a proof that a certain number matches BB(748). And such a proof is not easier than a direct proof of ZFC consistency, I presume. BTW, a value can't be uncomputable, only a function can.
- Kranar 3y ago
  It is categorically false that BB(748) is not computable. On the contrary any particular BB(n) can be computed by some Turing Machine even though there is no Turing Machine that can compute BB(n) for every n.
  - modeless 3y ago
    So then what's stopping you from running the BB(748) machine, getting the number, then running the ZFC machine and proving ZFC consistent or not?
    - Kranar 3y ago
      A proof of existence is not the same as a construction, so the fact that we know that there exists a TM that computes BB(748) does not mean that we know which specific TM does it or how to construct such a TM.

generic92034 3y ago

It is funny to me that you are going for BB(748) in this context when you could go for the much, much, ... lower number BB(745), as outlined in [0]. [0]: https://www.ingo-blechschmidt.eu/assets/bachelor-thesis-undecidability-bb748.pdf https://www.ingo-blechschmidt.eu/assets/bachelor-thesis-unde...

concordDance 3y ago

> Though we don't have the computing power for this currently I don't think you get how big BB748 is. To use a metaphor: If you took stuffed the entire observable universe full of computronium that can do more calculations in a fragment the size of a human cell than our entire civilization, then shrank that universe down to the size of a grain of sand and filled our entire universe with that, THEN did this once for every possible distinguishable person (ie. If you can say after a lifetime of detailed observation that person A isn't identical to person B then they're distinguishable) you still aren't even close to BB748. In fact, I'd be surprised if you're over BB10 and you're definitely under BB20.

reaperman 3y ago
BB(6) might be too large even to store (let alone compute) using all the mass and energy of the universe. I think the computable limit if you converted all the mass in the observable universe to energy (E = mc^2) would be BB(5), assuming adherence to the Laundauer Limit[0]. After calculating this I found a quote in wikipedia[1]: "There is not enough computational capacity in the known part of the universe to have performed even S(6) operations directly." That cited this paper[2], which is probably better than my model at utilizing the total available physics of the universe for calculation purposes. Anyways, the mass of the known universe is on the order of 10^56 grams[3]. Converting this all to energy using E=mc^2 yields on the order of 10^70 Joules (10^88 electron volts). Setting or clearing a single bit of information requires at minimum 0.018 eV. That allows about 10^90 bits. BB(6) may require on the order of 10^90^2 bit flips. So it is absolutely not computable using all the mass and energy in the universe. In fact, I don't think it's even storable using all the mass and energy in the universe. I don't really understand Busy Beaver, so if I got any of this wrong please correct me for the record. 0: https://en.wikipedia.org/wiki/Landauer%27s_principle https://en.wikipedia.org/wiki/Landauer%27s_principle 1: https://en.wikipedia.org/wiki/Busy_beaver https://en.wikipedia.org/wiki/Busy_beaver 2: https://arxiv.org/pdf/quant-ph/0110141.pdf https://arxiv.org/pdf/quant-ph/0110141.pdf 3: https://www.wolframalpha.com/input?i=mass+of+the+universe https://www.wolframalpha.com/input?i=mass+of+the+universe

contravariant 3y ago

A Turing machine which halts iff ZFC is consistent seems like it would be more interesting. In theory it would be possible to run it and show ZFC to be consistent that way. Although I imagine it suffers from the problem that it can only be shown to work within ZFC or any theory powerful enough to prove the consistency of ZFC, which tells us nothing.

martincmartin 3y ago

It's easy to generate all proofs in any system, just pick any axiom, then apply any inference rule, and repeat. So if you ever generate both P and not P, then you've proven its inconsistent. So if it's inconsistent, it's straight forward to prove. It's only if it's consistent that we can't prove it in any finite time.