5 ms·

They created a Turing machine that may run forever. However we can't prove that. It could stop the next second, or tomorrow, or the day after. They also proved

They created a Turing machine that may run forever. However we can't prove that. It could stop the next second, or tomorrow, or the day after. They also proved however that you'll never see it halt. Because that would be a proof of consistency. Wait. What?

tromp 10y ago
No; halting would be a proof of inconsistency. We expect it never to halt because we believe ZFC to be consistent.
- rrobukef 10y ago
  Belief has nothing to do with it. I can believe ZFC is inconsistent and the world will not change a bit. You can't prove me wrong. (It's almost a religious argument) If I believe the inconsistency of ZFC then I believe the machine must halt. I can't ever observe it since I can't know the number of steps needed. There's almost a paradox but not quite.
  - Grue3 10y ago
    No, if ZFC is inconsistent, then you can know the number of steps needed. Every statement, true or false, is derivable from ZFC if it is inconsistent. If there's contradiction in ZFC, it can be found in finite time by enumerating all the theorems.
deleted 10y ago
[deleted]
zodiac 10y ago
If you're refering to Yedidia and Aaronson's machine, the machine searches for counterexamples in ZFC. We believe, but cannot prove, that ZFC is consistent. Also, we can prove that assuming ZFC is consistent, ZFC cannot prove that ZFC is consistent. Hence, since we believe ZFC is consistent, we believe that the machine will not halt, but we can't prove it. This implies that BB(7910) cannot be computed.
- ikeboy 10y ago
  BB 7910 can be computed: it's just a finite number. What you mean is that the value can't be proven correct in ZFC.
  - zodiac 10y ago
    If you write down a value for BB 7910 but can't prove that it is correct, I wouldn't say that you "computed it".
    - ikeboy 10y ago
      But ZFC isn't the only system in town. It's possible (although highly unlikely) that we could prove its value in another system that we can see to be just as valid as ZFC. (Like adding consistency axioms and so on.)
      - zodiac 10y ago
        Yeah, sure, if we agree to do math in the system ZFC+Con(ZFC) we can prove that Yedidia's machine does not halt. But then we can just construct another machine (call it M', a n'-state turing machine) that searches for contradictions in ZFC+Con(ZFC), and now we believe that M' does not halt, but we can't prove it; and now, BB(n') can't be computed.
        ikeboy 10y ago
        Sure, but that n' will be larger.
        zodiac 10y ago
        Sure, but no matter what model of math we choose to work in, I can come up with some n such that I can say "...hence, BB(n) cannot be computed", and you cannot reply "BB(n) can be computed; it's just a finite number. What you mean is the value can't be proven correct..."

tromp 10y ago

No; halting would be a proof of inconsistency. We expect it never to halt because we believe ZFC to be consistent.

rrobukef 10y ago
Belief has nothing to do with it. I can believe ZFC is inconsistent and the world will not change a bit. You can't prove me wrong. (It's almost a religious argument) If I believe the inconsistency of ZFC then I believe the machine must halt. I can't ever observe it since I can't know the number of steps needed. There's almost a paradox but not quite.
- Grue3 10y ago
  No, if ZFC is inconsistent, then you can know the number of steps needed. Every statement, true or false, is derivable from ZFC if it is inconsistent. If there's contradiction in ZFC, it can be found in finite time by enumerating all the theorems.

deleted 10y ago

[deleted]

zodiac 10y ago

If you're refering to Yedidia and Aaronson's machine, the machine searches for counterexamples in ZFC. We believe, but cannot prove, that ZFC is consistent. Also, we can prove that assuming ZFC is consistent, ZFC cannot prove that ZFC is consistent. Hence, since we believe ZFC is consistent, we believe that the machine will not halt, but we can't prove it. This implies that BB(7910) cannot be computed.

ikeboy 10y ago
BB 7910 can be computed: it's just a finite number. What you mean is that the value can't be proven correct in ZFC.
- zodiac 10y ago
  If you write down a value for BB 7910 but can't prove that it is correct, I wouldn't say that you "computed it".
  - ikeboy 10y ago
    But ZFC isn't the only system in town. It's possible (although highly unlikely) that we could prove its value in another system that we can see to be just as valid as ZFC. (Like adding consistency axioms and so on.)
    - zodiac 10y ago
      Yeah, sure, if we agree to do math in the system ZFC+Con(ZFC) we can prove that Yedidia's machine does not halt. But then we can just construct another machine (call it M', a n'-state turing machine) that searches for contradictions in ZFC+Con(ZFC), and now we believe that M' does not halt, but we can't prove it; and now, BB(n') can't be computed.
      - ikeboy 10y ago
        Sure, but that n' will be larger.
        zodiac 10y ago
        Sure, but no matter what model of math we choose to work in, I can come up with some n such that I can say "...hence, BB(n) cannot be computed", and you cannot reply "BB(n) can be computed; it's just a finite number. What you mean is the value can't be proven correct..."