以文本方式查看主题

-  中文XML论坛 - 专业的XML技术讨论区  (http://bbs.xml.org.cn/index.asp)
--  『 理论计算机科学 』  (http://bbs.xml.org.cn/list.asp?boardid=64)
----  请教计算理论中的判断输出问题  (http://bbs.xml.org.cn/dispbbs.asp?boardid=64&rootid=&id=20507)

--  作者：magicspiral
--  发布时间：7/20/2005 11:03:00 AM

--  请教计算理论中的判断输出问题
弟初学.万请大佬们指教.
    计算理论中有个基础的概念:就是不能做出这样一个程序:这个程序可以判断所有程序是否输出某一特定字符串.
     我在刘田先生翻译的自动机理论语言和计算导论(Introduction to automata theory,languages,and computation )的217面看到有关证明.我没看懂.
    我对书中证明错误理解如下:
    假设有任意程序P1,P1输出YES.假设有能检验所有程序输出的程序:H2.H2的输入参数为任意的程序的代码.H2分析这些代码,如果认为输入的程序代码能输出YES,那么H2则输出NO.反之,则输出YES.
    现在将P1作为参数输入H2,那么H2将输出NO.
   将P1不作为参数,而作为H2的一个变量写到H2中去.这个更改不失一般性.
    现在将H2的代码作为参数输入到H2去.那么现在H2输出的是YES
   H2的两次输出矛盾
   所以H2不存在

以上我的理解肯定是错的．因为我认为第一次的H2和第二次的H2输入是不一样的,所以得出不同的输出不导致矛盾.
那么到底该如何理解?请各位大佬指教!

--  作者：ljb
--  发布时间：8/5/2005 11:18:00 PM

--  
这样经典的书看英文版拉，
实话，中文翻译一般是垃圾。。。。。
而且这本有英文影印
--  作者：Logician
--  发布时间：8/6/2005 3:17:00 PM

--  
以下是引用magicspiral在2005-7-20 11:03:27的发言：
     现在将H2的代码作为参数输入到H2去.那么现在H2输出的是YES
    H2的两次输出矛盾
    所以H2不存在


不是这样的。
H2的功能是：判断一个以P为输入并以P为代码的程序是否输出NO。如果是，H2就输出YES，反之输出NO。
这时，若把H2自己输入给H2，则H2既不能输出YES，也不能输出NO。

用书上的描述，H2在收到H2时的运行过程是这样的：
1、H2把收到的H2代码保存在数组A了。
2、H2模拟H1，去分析A里的代码。得到一个结果，YES/NO。这个结果的意思是：“当H2这个程序收到H2时，会输出NO/YES。”。
3、H2输出这个结果（YES/NO）。

但这个结果却和H1的判断相反。
也即，H1是不正确的。

--  作者：magicspiral
--  发布时间：8/11/2005 1:14:00 AM

--  
谢谢LOGICIAN,你说得很清楚,这下明白了.
--  作者：frozenbbs
--  发布时间：8/22/2005 3:41:00 PM

--  
一般性的验证问题是不能实现的。
W 3 C h i n a ( since 2003 ) 旗 下 站 点
苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》
 78.125ms