4 ms·

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. Als

by 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..."
        ikeboy 10y ago
        It can always be computed. If you're choosing a specific model of math, you need to specify that in your statement. It will still be computable within that model, just not provably so within that model. Computable has a very specific meaning in computability theory, and any finite number is computable. The function BB(n) is not computable, but this was known for decades, it has nothing to do with the recent result.
        zodiac 10y ago
        > If you're choosing a specific model of math, you need to specify that in your statement. I mean, in my most recent statement I quantified over all consistent models... > It will still be computable within that model, just not provably so within that model. OK, now I'm confused; what is the specific definition of "computable number" you're using? Also, informally speaking, say we're both working in ZFC. You claim that BB(7910) is computable. What does that mean? Does it mean you can write down its value as a normal decimal number?
        ikeboy 10y ago
        >I mean, in my most recent statement I quantified over all consistent models... Not quite, as I pointed out in https://news.ycombinator.com/item?id=11753020 https://news.ycombinator.com/item?id=11753020. You can easily have a consistent system that proves the value of all BB numbers, it just won't be computable. If you restrict us to computable consistent systems, then for any given model there will be some value of BB it doesn't prove, but also for any given value of BB there will be some consistent model that proves it. There's nothing in particular added about knowability by Aaronson's et al result, only about provability. >OK, now I'm confused; what is the specific definition of "computable number" you're using? https://en.wikipedia.org/wiki/Computable_number https://en.wikipedia.org/wiki/Computable_number Any finite number is computable, we just can't prove that a specific machine is the one that computes BB(N). We can prove that some machine in a finite set (all TMs of size N we haven't seen to halt or proven nonhalting) computes it, but we can't pin down which one, within that model. >Also, informally speaking, say we're both working in ZFC. You claim that BB(7910) is computable. What does that mean? Does it mean you can write down its value as a normal decimal number? Lol nope. We can't even write down anything above BB(6). BB(7) has more digits than atoms in the observable universe. My claim that BB(7910) is computable means there's a Turing machine that computes it. That's easy to prove, as any finite integer can be computed by a Turing machine. There's no Turing machine that computes every BB number sequentially, though.

by zodiac 10y ago

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..."
        ikeboy 10y ago
        It can always be computed. If you're choosing a specific model of math, you need to specify that in your statement. It will still be computable within that model, just not provably so within that model. Computable has a very specific meaning in computability theory, and any finite number is computable. The function BB(n) is not computable, but this was known for decades, it has nothing to do with the recent result.
        zodiac 10y ago
        > If you're choosing a specific model of math, you need to specify that in your statement. I mean, in my most recent statement I quantified over all consistent models... > It will still be computable within that model, just not provably so within that model. OK, now I'm confused; what is the specific definition of "computable number" you're using? Also, informally speaking, say we're both working in ZFC. You claim that BB(7910) is computable. What does that mean? Does it mean you can write down its value as a normal decimal number?
        ikeboy 10y ago
        >I mean, in my most recent statement I quantified over all consistent models... Not quite, as I pointed out in https://news.ycombinator.com/item?id=11753020 https://news.ycombinator.com/item?id=11753020. You can easily have a consistent system that proves the value of all BB numbers, it just won't be computable. If you restrict us to computable consistent systems, then for any given model there will be some value of BB it doesn't prove, but also for any given value of BB there will be some consistent model that proves it. There's nothing in particular added about knowability by Aaronson's et al result, only about provability. >OK, now I'm confused; what is the specific definition of "computable number" you're using? https://en.wikipedia.org/wiki/Computable_number https://en.wikipedia.org/wiki/Computable_number Any finite number is computable, we just can't prove that a specific machine is the one that computes BB(N). We can prove that some machine in a finite set (all TMs of size N we haven't seen to halt or proven nonhalting) computes it, but we can't pin down which one, within that model. >Also, informally speaking, say we're both working in ZFC. You claim that BB(7910) is computable. What does that mean? Does it mean you can write down its value as a normal decimal number? Lol nope. We can't even write down anything above BB(6). BB(7) has more digits than atoms in the observable universe. My claim that BB(7910) is computable means there's a Turing machine that computes it. That's easy to prove, as any finite integer can be computed by a Turing machine. There's no Turing machine that computes every BB number sequentially, though.