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机有关的下列问题是不可判定的

1. 给定Turing机M和输入字符串w，M是否在输入w上停机？
2. 给定Turing机M，M是否在空带上停机？
3. 给定Turing机M，究竟有没有M在上面停机的字符串？
4. 给定Turing机M，M是否在每一个输入字符串上都停机？
5. 给定两台Turing机M1和M2，它们是否在同样的字符串上都停机？
6. 给定Turing机M，M半判定的语言是否正则？是否上下文无关？是否递归？
7. 存在某台固定机器Turing机M0，对它下列问题是不可判定的：给定w，M0是否在w上停机？

定理：下列每个问题都是不可判定的：

1. 对给定的文法G和字符串w，判定是否<<latex: execution failed [Missing parentheses in call to 'print'. Did you mean print(...)?] (see also the log)>>

2. 对给定的文法G，判定是否<<latex: execution failed [Missing parentheses in call to 'print'. Did you mean print(...)?] (see also the log)>>

3. 对两个给定的文法G1和G2，判定是否L(G1)=L(G2)

4. 对任意的文法G，判定是否<<latex: execution failed [Missing parentheses in call to 'print'. Did you mean print(...)?] (see also the log)>>

5. 存在某个固定的文法G0，判断任意给定的字符串w是否属于L(G0)

定理：下列每个问题都是不可判定的：

1. 给定上下文无关文法G，是否<<latex: execution failed [Missing parentheses in call to 'print'. Did you mean print(...)?] (see also the log)>>？

2. 给定两个上下文无关文法G1和G2，是否L(G1)=L(G2)？
3. 给定两台下推自动机M1和M2，它们是否恰好接受同样的语言？
4. 给定下推自动机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)>>？