4 ms·

BB(748) is a finite integer, and all things finite can by definition be computed (in computational theory). Uncomputable things must be of an infinite nature, s

by tromp 5y ago

BB(748) is a finite integer, and all things finite can by definition be computed (in computational theory). Uncomputable things must be of an infinite nature, such as functions from the natural numbers to a boolean, or languages of binary strings.

dandanua 5y ago
That's what I'm talking about, you can't say that BB(748) is uncomputable.
- lilyball 5y ago
  Surely “uncomputable” here means “uncomputable in ZFC”, no? The fact that you’ve found it in a stronger theory doesn’t matter, because the value now depends on that stronger theory and may be wrong in ZFC.
  - jimhefferon 5y ago
    What's been shown is that, where the number is n, the fact that it equals n cannot be proved in ZFC. Of course it can be proved in a theory with more axioms. In particular, take ZFC and add the statement as an axiom.
  - dandanua 5y ago
    > the value now depends on that stronger theory The value of every BB(n) is well-defined in ZFC. It can't change if we consider a stronger (and consistent) theory than ZFC. Proving that BB(n) equals to a concrete integer is a different matter – it's either possible or not within your theory.
    - lilyball 5y ago
      When I say "the value now depends" I mean the value you computed in that stronger theory is not computable in the weaker one, and therefore the computation depends on the stronger theory, and therefore the value is only correct if the stronger theory is consistent.
  - SilasX 5y ago
    Not when you clarify that you mean "not computable at all" by adding the "at all", as the reddit poster did.
dwohnitmok 5y ago
Strictly speaking saying a single natural number is "computable" is a category error. Only functions can be computable or noncomputable. All other notions of computability must be reduced to a function on the natural numbers (e.g. recognition problems are shorthand for functions on the natural numbers that have a range of {0, 1}).

by tromp 5y ago

dandanua 5y ago

That's what I'm talking about, you can't say that BB(748) is uncomputable.

lilyball 5y ago
Surely “uncomputable” here means “uncomputable in ZFC”, no? The fact that you’ve found it in a stronger theory doesn’t matter, because the value now depends on that stronger theory and may be wrong in ZFC.
- jimhefferon 5y ago
  What's been shown is that, where the number is n, the fact that it equals n cannot be proved in ZFC. Of course it can be proved in a theory with more axioms. In particular, take ZFC and add the statement as an axiom.
- dandanua 5y ago
  > the value now depends on that stronger theory The value of every BB(n) is well-defined in ZFC. It can't change if we consider a stronger (and consistent) theory than ZFC. Proving that BB(n) equals to a concrete integer is a different matter – it's either possible or not within your theory.
  - lilyball 5y ago
    When I say "the value now depends" I mean the value you computed in that stronger theory is not computable in the weaker one, and therefore the computation depends on the stronger theory, and therefore the value is only correct if the stronger theory is consistent.
- SilasX 5y ago
  Not when you clarify that you mean "not computable at all" by adding the "at all", as the reddit poster did.

dwohnitmok 5y ago

Strictly speaking saying a single natural number is "computable" is a category error. Only functions can be computable or noncomputable. All other notions of computability must be reduced to a function on the natural numbers (e.g. recognition problems are shorthand for functions on the natural numbers that have a range of {0, 1}).