&gt; The source for the Turing Halting problem is Gödel&#x27;s incompleteness theorems, which do specify that the entities to which it applies are non-trivial. The Turing Halting problem, and Gödel&#x27;s incompleteness theorems, are deeply connected.<p>Gödel doesn&#x27;t say anything about &quot;non-trivial&quot; any more than Turing does. His first theorem is a &quot;there exists at least one statement&quot; thing, just like the halting problem. Like the halting problem, the proof is a proof by construction, but that statement is not a statement that anyone would a priori are to prove, just like the program &quot;If I halt, run forever&quot; is not a program that anyone would particularly want to run. So while yes, they&#x27;re deeply connected, from the point of view of proving actual systems correct, it&#x27;s not clear they matter. And neither theorem says anything about &quot;non-trivial&quot; statements&#x2F;programs (just about non-trivial <i>formalizations</i> and <i>languages</i>).<p>Gödel&#x27;s second theorem is super relevant, though: it says that any consistent system cannot prove its own consistency. But that&#x27;s fine. Coq itself is implemented in a Turing-complete language (ML), not in Coq. It would be nice if we could verify Coq in Coq itself, but since Gödel said we can&#x27;t, we move on with life, and we just verify other things besides proof assistants. (And it seems to be worthwhile to prove things correct in a proof assistant, even without a computer-checked proof of that proof assistant&#x27;s own correctness.)<p>This is not waving away the problem, it&#x27;s acknowledging it and working within the limits of the problem to do as much as possible. And while that&#x27;s not everything, it turns out a lot of stuff of practical importance -- perhaps <i>everything</i> of practical importance besides proving the system complete in its own language -- is possible.