3 ms·

Computability is not the same thing as proof. “Not computable” means “no program which is known to halt can answer this”.

• dandanua 5y ago
  No, "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 ago
    The 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 ago
      First, 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).