News for hackers. Stuff that matters.
Re:Gödel's Theorem by dvt on Thursday January 31, 2019 @03:06AM (#19043258)
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"
Re:Gödel's Theorem by dvt on Thursday January 31, 2019 @04:00AM (#19043463)
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)).
Re:Gödel's Theorem by niklasd on Thursday January 31, 2019 @04:11AM (#19043507)
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