我们这学期学习理论计算机科学
但是,老师是新来的,有些问题他也无法解答,哎!我想知道这个停机问题的证明:
概念: HALT(x,y)表示以y为代码的程序对输入x的计算最终停止问题:"HALT(x,y)和HALT(x,x)不是计算的"这一定理的证明-----------------------------------------------------------
//书上的证明如下:
证:只需证HALT(x,x)不是可计算的,假设不然,则可构造程序P如下:
[A] IF HALT(X,X) GOTO A
后面的东西我也明白，就是不知道这里这程序是怎么构造出来的
为什么要这样构造，我根本看不出来这样的函数具有可计算性-------------------------------------------------------------
哎，开这门课程的学校可能很少，只好碰碰运气了
但是,老师是新来的,有些问题他也无法解答,哎!我想知道这个停机问题的证明:
概念: HALT(x,y)表示以y为代码的程序对输入x的计算最终停止问题:"HALT(x,y)和HALT(x,x)不是计算的"这一定理的证明-----------------------------------------------------------
//书上的证明如下:
证:只需证HALT(x,x)不是可计算的,假设不然,则可构造程序P如下:
[A] IF HALT(X,X) GOTO A
后面的东西我也明白，就是不知道这里这程序是怎么构造出来的
为什么要这样构造，我根本看不出来这样的函数具有可计算性-------------------------------------------------------------
哎，开这门课程的学校可能很少，只好碰碰运气了
你觉得程序中的函数和数学中的函数有那里不同呢如果没有不同的话，数学的推理过程和图灵机的运算过程有什么区别呢----------
“HALT(x,y)表示以y为代码的程序对输入x的计算最终停止”
这句话用计算机的程序语言解释一遍：
HALT(x,y)中的传入参数为x 和y 时，会抛出一个无法拦截的异常，导致死机
其中的x的类型为‘输入’，y的类型为‘代码’ // 某些脚本类语言是不检查函数的类型的
证:只需证HALT(x,x)不是可计算的,假设不然,则可构造程序P如下:
[A] IF HALT(X,X) GOTO A我想知道的是，那个程序如何构造出来，也就是说所构造出来的程序一看就觉得它不可计算
我想知道这个程序怎么体现“假设不然(也就是说，可以构造一个可计算的程序）”这句话的
> 那个程序如何构造出来，也就是说所构造出来的程序一看就觉得它不可计算也许作者实验了几百次才写出了这个证明过程
我觉得：只要理解证明过程的的正确性就够了-------
> 这个程序怎么体现“假设不然(也就是说，可以构造一个可计算的程序）”这句话的注意“图灵机”的定义
而HALT是：HALT(x,y)中的传入参数为x 和y 时，会抛出一个无法拦截的异常，导致死机
你说这个HALT()这个函数应该出现在图灵机代码中么
首先，谢谢你能够帮助
你只是给我讲出了图灵机的停机问题
当然，我所提出的问题与它有相通性，但是，我现在想要知道的是那个证明过程如何而来
我看那个证明过程的时候看不懂。对于任何一个程序，都可以用一个自然数来表示（这牵涉到一种编码机制）
然后，用一个自然数y表示一个程序，对于程序y和输入x，它是否会计算终止
也就是HALT(x,y)是否为真（或是否停机）。这是不可计算的
然后，书上给出了证明过程如上我不知道那个反设而得出的程序怎么体现反设本身的，也就是说，它假设那个问题可计算
然而给出的却是一个不可计算的程序。我只想把这个过程搞清楚，不想跟图灵机牵上关系。谢谢你，Panr(光荣）
１、程序设计语言Ｊ：
语言Ｊ使用三种变量：输入变量，输出变量，中间变量
语言Ｊ使用三种类型的语句：
（１）增量语句：V←V+1
（２）减量语句：V←V-1
（３）条件转移语句：IF V≠0 GOTO A
如下所示一个Ｊ语言程序Ｐ：
[A] X←X-1
Y←Y+1
IF X≠0 GOTO A
程序的输入变量是Ｘ，输出变量是Ｙ，没有中间变量
在程序执行以前应该给出输入变量一个值，其余的变量值规定为０ 这个程序计算如下的函数： f(x)=x (若x>0) 否则 f(x)=1 （我只是简单地说明这个概念，应该默认你明白这个概念，所以我没有作更多的描述） ２、一种程序的编码方法：
可以通过配对函数和 Gödel 数的编码来实现如下功能：
１）任何一个Ｊ程序都可以用一个自然数来表示
２）任何一个自然数都可以表示一个Ｊ程序
也就是说，Ｊ程序可以与自然数建立一个一一对应的关系
对于一个Ｊ程序Ｐ，它的自然数编码为 y=#(P) ３、HALT(x,y)表示以y为代码的Ｊ程序对输入x（x 是以 y 为编码的Ｊ程序的输入变量）的计算最终停止
上面y是一种自然数编码，它对应着一个Ｊ语言程序Ｐ
程序Ｐ的输入变量为 x下面进入正题：
（书中给出了一个定理及其证明：）
HALT(X,Y)与 HALT(X,X)不是可计算的 证：只需证HALT(X,X)不是可计算的，假设不然，则可构造程序P如下：
[A] IF HALT(X,X) GOTO A
显然，
程序所计算的结果为：
0 若¬HALT(X,X)
无定义 基HALT(X,X). 记#(P)=a，则对任意x ，有
HALT(x,a) <=> 程序所计算的结果=0 <=> ¬HALT(x,x)
(上面<=>为等价于)
令x=a,得
HALT(a,a)<=>¬HALT(a,a)
矛盾.
证讫.
我看不懂它的证明过程呵呵！！！！！！
HALT(x,a) <=> 程序所计算的结果=0 //<= 这个等价是那里来的
因为我的理解中：
“程序”是指“[A] IF HALT(X,X) GOTO A”
它的要求中两个输入是同值的，而“HALT(x,a)”的两个输入并不相同，“HALT(x,a)”根本就不可以代入到“程序”中不明白作者怎么得出这个等价符号的
图灵机就是理论计算机的一个例子，通过对比例子才可能准确理解乃至学以至用“图灵机”好呀，你要弄知道最初的理论计算就是以图灵机为研究工具的
http://episte.math.ntu.edu.tw/articles/sm/sm_30_11_2/index.html
那么这个问题我还是先放下吧
等看到图灵机章节之后再回头研究THANK YOU！