Turing Incompleteness Theorem

The TuringIncompletenessTheorem is a theorem that reads "There are no nontrivial questions about the result of a Turing machine that can be answered by a Turing machine for all Turing machines."

See HaltingProblem for why this is true.

It's better known as RicesTheorem.

[Ah yes. From the other size of The ChurchTuringThesis.]

There are several ways to prove it, of course, but the one I'm most familiar is to reduce it to the HaltingProblem. How does that make it the "other size[side?] of the ChurchTuringThesis"?

[Because RicesTheorem is based from lambda calculus. I believe the fact of identical theorems with both mechanisms was instrumental in proving the ChurchTuringThesis.]

It's not. It's based on TMs. Now one can also prove it based on LambdaCalculus, KleenesHierarchy?, and some other things, but it's usually done in terms of TMs.