Hacker News new | ask | show | jobs
by ykonstant 1258 days ago
The way you are phrasing your question is confusing; without the parenthesis, your two statements are identical. The only meaningful way to interpret "The whole thing is undecidable" is whether you can or cannot decide all (infinitely many) statements at once.

If that is what you mean, then yes: take any undecidable Diophantine equation Q=0 of, say, n variables. Consider the sequence of yes/no problems P_K = {Is there a solution to Q=0 in [-K,K]^n?} parametrized by a positive integer K. Each of those problems is decidable in isolation, but the totality cannot be, since that would decide if Q=0 has a solution or not.

1 comments

Thank you for suggesting this example.

For the undecidable Diophantine equation Q=0 of n variables - I'm assuming that the fact that someone could hit a solution randomly (by randomly generating the n variables and getting lucky) does not contradict with its undecidability.

Still I'm not clear what happens if such a solution would be randomly hit for an equation that's mapped to another hard question such as ZFC consistency. It would imply that a question such as ZFC consistency could be solved by randomly generating an answer, which seemingly doesn't make sense?