4 ms·

We might know it†, but we can't prove it† (because proving it implies computing it). † The knowing is external to the system at hand, and the proving is intern

• ginnungagap 8y ago
  Define (inside the system) the function S(1)=14 and S(n+1)=g(n) for all n\geq1 where g is any function which is not computable. I'm not convinced you can jump from "the function is uncomputable" to "the system cannot determine a single value of the function"
  • dvt 8y ago
    I see what you're saying, and yeah, I think you're right. You can construct a non-computable function S(n) that returns n when n is even, but does something non-computable when n is odd (kind of like f_bar). Of course, we're not really interested in these degenerate cases where n is even, but rather in the cases where we know that there's some kind of answer we can't prove in the system. I gave "S(1) = 0" as an example (you can replace '1' with whatever argument ends up being non-computable in your case, maybe S(2)).
• niklasd 8y ago
  To add to what the other commenter said: Isn't the Busy beaver function uncomputable and we still can obtain some values for small n and prove that they are correct [1]? So I'm not sure it only applies to some special cases, I think several relevant incomputable problems might have this characteristic. [1] https://en.wikipedia.org/wiki/Busy_beaver#Non-computability https://en.wikipedia.org/wiki/Busy_beaver#Non-computability