"不可判定性"版本比较

版本2和3间的区别

Church-Turing论题：在所有的输入上停机的Turing机作为与“算法”的直觉化概念相对应的精确的形式化概念。

通用Turing机

停机问题：

定理：语言latex($$H=\lbrace "M""\omega":Turing\ Machine\ M\ halts\ on\ input\ string\ \omega\rbrace$$)不是递归的；所以，递归语言类是递归可枚举语言类的真子集。

定理：递归可枚举语言类载补运算下不封闭。

定义：归约

定理：若L1不是递归的，并且存在从L1到L2的归约，则L2也不是递归的。

定理：与Turing机有关的下列问题是不可判定的

-  ⇤ ← 于2006-03-26 15:07:41修订的的版本2 → 
  大小: 559
  编辑: 60
  备注:
+   ← 于2006-03-26 15:46:30修订的的版本3 → ⇥
  大小: 1208
  编辑: 60
  备注:
-删除的内容标记成这样。
+加入的内容标记成这样。
 行号 15:
+定理：与Turing机有关的下列问题是不可判定的
   1. 给定Turing机M和输入字符串w，M是否在输入w上停机？
   1. 给定Turing机M，M是否在空带上停机？
   1. 给定Turing机M，究竟有没有M在上面停机的字符串？
   1. 给定Turing机M，M是否在每一个输入字符串上都停机？
   1. 给定两台Turing机M1和M2，它们是否在同样的字符串上都停机？
   1. 给定Turing机M，M半判定的语言是否正则？是否上下文无关？是否递归？
   1. 存在某台固定机器Turing机M0，对它下列问题是不可判定的：给定w，M0是否在w上停机？