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.''