博文
再谈非确定性图灵机的概念
|||
再谈非确定型图灵机的概念
姜咏江
研究千禧大奖头号难题p与np问题，最难让人理解的是非确定性图灵机的概念。非确定型图灵机并不是任意一个图灵机这种概念，而是在一个确定型图灵机存在的情况下，用读入字符可能是图灵机带上任意一个字符，来确定某个猜测的结果是否是该图灵机实际运算结果的计算方式的概念。
下表是一个或运算图灵机，假定其带子上只允许出现空格、0和1，那么用这个图灵机运算需要在带子上事先写上参加运算的数码0或1。由于这是一个二元运算，故计算出结果需要2次输入，即需要2次状态演变才能输出结果。即状态变化或者为b→c，或者为b→d。
或运算 | 结果 | 状态 转移 | ||
前状态 | 读入 | 写输出 | 后状态 | |
b |
| R | b | b→b |
0 |
| c | b→c | |
1 |
| d | b→d | |
c |
|
| b | c→b |
0 | R,P0 | b | c→b | |
1 | R,P1 | b | c→b | |
d |
|
| b | d→b |
0 | R,P1 | b | d→b | |
1 | R,P1 | b | d→b | |
能够确定一个图灵机运算结果的状态数，我们不妨称为状态演变层次。二元运算有2个层次，n元运算一般应该有n个层次。
针对这个确定型图灵机我们要回答数码2是不是这个图灵机的运算结果？我们该如何做呢？在我们已经知道其结果只能是｛0，1｝这个集合中的数，也就是用2能够直接与结果集合元素比较的时候，就可以给出确定的回答。但是在我们都不知道这个图灵机运算结果的情况下，如何来验证？这就需要分层对可能输入的字符进行验证。具体地说，先要在b状态下考虑输入是0，再到c状态下考虑输入是0，运算的结果是不是2（下图的红线）；如果结果不是2，再在c状态考虑输入是1的情况（下图的橙线）。
图1 非确定型图灵机上的猜测验证
如果从b状态0输入出发未得到结果是2的答案，则还要从b状态输入是1的情况出发再去逐层验证，这样会有图中的蓝线和浅蓝线表示的情况。
确定型图灵机如果是n元运算，那么状态是层次也应该是n，其中运算的中间结果也应该在带子字符集当中，状态输出字符可以打印之后，再做为下一状态的输入字符。做为n元运算的非确定性图灵机，每个状态的转移仍然受字符集的限制。如果带子上的字符集有k个不同字符，那么猜测运算结果的查找象图1那样，最多可能进行kn次，这样才能够确定给出的结果是否是该图灵机能够计算出的结果。
2015-5-11
https://blog.sciencenet.cn/blog-340399-889322.html
上一篇：在ipad上如何修改或撰写较长的科学网博文？
下一篇：今天去参加了中关村创新论坛大会
