Church-Turing论题：在所有的输入上停机的Turing机作为与“算法”的直觉化概念相对应的精确的形式化概念。
通用Turing机
停机问题：
定理：语言<<latex: execution failed [Missing parentheses in call to 'print'. Did you mean print(...)?] (see also the log)>>不是递归的；所以，递归语言类是递归可枚举语言类的真子集。
定理：递归可枚举语言类载补运算下不封闭。
定义：归约
定理：若L1不是递归的，并且存在从L1到L2的归约，则L2也不是递归的。
定理：与Turing机有关的下列问题是不可判定的
- 给定Turing机M和输入字符串w，M是否在输入w上停机？
- 给定Turing机M，M是否在空带上停机？
- 给定Turing机M，究竟有没有M在上面停机的字符串？
- 给定Turing机M，M是否在每一个输入字符串上都停机？
- 给定两台Turing机M1和M2，它们是否在同样的字符串上都停机？
- 给定Turing机M，M半判定的语言是否正则？是否上下文无关？是否递归？
- 存在某台固定机器Turing机M0，对它下列问题是不可判定的：给定w，M0是否在w上停机？
定理：下列每个问题都是不可判定的：
对给定的文法G和字符串w，判定是否<<latex: execution failed [Missing parentheses in call to 'print'. Did you mean print(...)?] (see also the log)>>
对给定的文法G，判定是否<<latex: execution failed [Missing parentheses in call to 'print'. Did you mean print(...)?] (see also the log)>>
- 对两个给定的文法G1和G2，判定是否L(G1)=L(G2)
对任意的文法G，判定是否<<latex: execution failed [Missing parentheses in call to 'print'. Did you mean print(...)?] (see also the log)>>
- 存在某个固定的文法G0，判断任意给定的字符串w是否属于L(G0)
定理：下列每个问题都是不可判定的：
给定上下文无关文法G，是否<<latex: execution failed [Missing parentheses in call to 'print'. Did you mean print(...)?] (see also the log)>>？
- 给定两个上下文无关文法G1和G2，是否L(G1)=L(G2)？
- 给定两台下推自动机M1和M2，它们是否恰好接受同样的语言？
- 给定下推自动机M，找出状态数最少的等价的下推自动机
不可解的铺砖问题
定理：给定铺砖系统，判定是否存在根据这个系统的铺砖，这个问题是不可判定的。
定理：语言是递归的当且仅当它和它的补都是递归可枚举的。
定义：Turing机M枚举语言L当且仅当对M的某个固定状态q，<<latex: execution failed [Missing parentheses in call to 'print'. Did you mean print(...)?] (see also the log)>>。语言是Turing可枚举的当且仅当存在枚举它的Turing机。
定理：语言是递归可枚举的当且仅当它是Turing可枚举的。
定义：以字典序Turing可枚举。
定理：语言是递归的当且仅当它是以字典序Turing可枚举的。
Rice定理：假设R是所有递归可枚举语言组成的类的非空真子集，那么下列问题是不可判定的：给定Turing机M，是否<<latex: execution failed [Missing parentheses in call to 'print'. Did you mean print(...)?] (see also the log)>>？