See https://news.ycombinator.com/item?id=34384838, I think it disproves your last sentence — at least when assuming that all solutions and all proofs of non-existence of a solution are expressible in a shared formal language.