|
大小: 1208
备注:
|
大小: 1632
备注:
|
| 删除的内容标记成这样。 | 加入的内容标记成这样。 |
| 行号 24: | 行号 24: |
定理：下列每个问题都是不可判定的： 1. 对给定的文法G和字符串w，判定是否[[latex($$\omega\in L(G)$$)]] 1. 对给定的文法G，判定是否[[latex($$e\in L(G)$$)]] 1. 对两个给定的文法G1和G2，判定是否L(G1)=L(G2) 1. 对任意的文法G，判定是否[[latex($$L(G)=\phi$$)]] 1. 存在某个固定的文法G0，判断任意给定的字符串w是否属于L(G0) |
Church-Turing论题：在所有的输入上停机的Turing机作为与“算法”的直觉化概念相对应的精确的形式化概念。
通用Turing机
停机问题：
定理：语言latex($$H=\lbrace "M""\omega":Turing\ Machine\ M\ halts\ on\ input\ string\ \omega\rbrace$$)不是递归的；所以，递归语言类是递归可枚举语言类的真子集。
定理：递归可枚举语言类载补运算下不封闭。
定义：归约
定理：若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($$\omega\in L(G)$$)
对给定的文法G，判定是否latex($$e\in L(G)$$)
- 对两个给定的文法G1和G2，判定是否L(G1)=L(G2)
对任意的文法G，判定是否latex($$L(G)=\phi$$)
- 存在某个固定的文法G0，判断任意给定的字符串w是否属于L(G0)