Re:Gödel's Theorem
by ginnungagap on Thursday January 31, 2019 @02:57AM
(#19043221)
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
[ Parent
| on HN ]
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 internal to the system at hand. I go into detail about this in my blog posts linked above.
Re:Gödel's Theorem
by ginnungagap on Thursday January 31, 2019 @03:25AM
(#19043323)
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"
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)).
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