Church-Turing论题：在所有的输入上停机的Turing机作为与“算法”的直觉化概念相对应的精确的形式化概念。
通用Turing机
停机问题：
定理：语言latex($$H=\lbrace "M""\omega":Turing\ Machine\ M\ halts\ on\ input\ string\ \omega\rbrace$$)不是递归的；所以，递归语言类是递归可枚举语言类的真子集。
定理：递归可枚举语言类载补运算下不封闭。
定义：归约
定理：若L1不是递归的，并且存在从L1到L2的归约，则L2也不是递归的。