3 ms·
I'm confused by your statement, there's plenty of not computable functions for which we know whether S(1)=0 is true or not
by ginnungagap 8y ago
I'm confused by your statement, there's plenty of not computable functions for which we know whether S(1)=0 is true or not
- dvt 8y agoWe 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 internal to the system at hand. I go into detail about this in my blog posts linked above.
- ginnungagap 8y agoDefine (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 agoI 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 agoTo 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