4 ms·
That reddit comment is very nice, though a little bit misleading at the end. > I can define this finite integer with only 7 characters, BB(748), but it can't b
by dandanua 5y ago
That reddit comment is very nice, though a little bit misleading at the end.
> I can define this finite integer with only 7 characters, BB(748), but it can't be computed at all!
is not true. The correct value of BB(748) can't be proved in ZFC, that's true. But we can use a stronger theory. For example, we can take the statement that ZFC is consistent, denoted by Con(ZFC), and add it to ZFC. The new theory ZFC+Con(ZFC) is stronger. So, it could be that ZFC+Con(ZFC) can prove BB(748).
If necessary, we can consider even stronger theory, e.g. ZFC+Con(ZFC)+Con(ZFC+Con(ZFC)).
- danielheath 5y agoComputability is not the same thing as proof. “Not computable” means “no program which is known to halt can answer this”.
- dandanua 5y agoNo, "not computable" is a property of functions that can accept infinite number of inputs. We can't say that a particular function value is uncomputable, there is no such definition. BB is uncomputable as a function. Yet, we can prove some of its values, because we can prove that some small Turing machines are not halting. To show that something runs forever you have to prove it.
- singularity2001 5y agoThe reddit edit is a bit misleading, your answer clarified the situation, thanks. But wouldn't the program BB(n){ if(n==748) return bb_748 else ... } be a computable emulation?
- codeflo 5y agoFirst, programs are defined to be finite in length. Second, for a program to be said to compute a function, it must do so for all possible inputs. That’s by definition, but there are good reasons why these definitions are useful: if we accept infinite or incomplete programs, everything would be considered computable. Anyway, your program can only compute BB for a finite number of inputs (depending on how far you bother to expand the “else …” part).
- tromp 5y agoBB(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 agoThat's what I'm talking about, you can't say that BB(748) is uncomputable.
- lilyball 5y agoSurely “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 agoWhat'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 agoWhen 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.
- deleted 5y ago[deleted]
- SilasX 5y agoYes! The comment is also wrong because defining BB(748) requires defining busy beaver functions, which take more than those seven characters. I was going to reply to say that on the Reddit thread but it’s over a year old and doesn’t accept new comments.