|
⇤ ← 于2006-03-20 21:30:42修订的的版本1
大小: 69
备注:
|
大小: 559
备注:
|
| 删除的内容标记成这样。 | 加入的内容标记成这样。 |
| 行号 1: | 行号 1: |
| {{{ #!latex \begin{equation} int_a^b f(x)dx \end{equation} }}} |
Church-Turing论题：在所有的输入上停机的Turing机作为与“算法”的直觉化概念相对应的精确的形式化概念。 通用Turing机 停机问题： 定理：语言[[latex($$H=\lbrace "M""\omega":Turing\ Machine\ M\ halts\ on\ input\ string\ \omega\rbrace$$)]]不是递归的；所以，递归语言类是递归可枚举语言类的真子集。 定理：递归可枚举语言类载补运算下不封闭。 定义：归约 定理：若L1不是递归的，并且存在从L1到L2的归约，则L2也不是递归的。 |
Church-Turing论题：在所有的输入上停机的Turing机作为与“算法”的直觉化概念相对应的精确的形式化概念。
通用Turing机
停机问题：
定理：语言latex($$H=\lbrace "M""\omega":Turing\ Machine\ M\ halts\ on\ input\ string\ \omega\rbrace$$)不是递归的；所以，递归语言类是递归可枚举语言类的真子集。
定理：递归可枚举语言类载补运算下不封闭。
定义：归约
定理：若L1不是递归的，并且存在从L1到L2的归约，则L2也不是递归的。