4 ms·
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
by 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 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).