“停机问题”的版本间的差异

来自计算思维百科
跳转至: 导航搜索
第3行: 第3行:
 
== 基本概念 ==
 
== 基本概念 ==
  
 停机问题(halting problem)是目前逻辑学的焦点, 第三次数学危机的解决方案。其本质问题是: 给定一个图灵机 T,和一个任意语言集合 S, 是否 T 会最终停机于每一个s∈S。其意义相同于可确定语言。显然任意有限 S 是可判定性的,可列的(countable) S 也是可停机的。
+
 停机问题(halting problem)是目前逻辑学的焦点, 也是 第三次数学危机的解决方案。其本质问题是: 给定一个图灵机 T,和一个任意语言集合 S, 是否 T 会最终停机于每一个s∈S。其意义相同于可确定语言。显然任意有限 S 是可判定性的,可列的(countable) S 也是可停机的。
  
 
 通俗的说,停机问题就是判断任意一个程序是否会在有限的时间之内结束运行的问题。如果这个问题可以在有限的时间之内解决,则有一个程序判断其本身是否会停机并做出相反的行为,这时候显然不管停机问题的结果是什么都不会符合要求。所以这是一个不可解的问题。
 
 通俗的说,停机问题就是判断任意一个程序是否会在有限的时间之内结束运行的问题。如果这个问题可以在有限的时间之内解决,则有一个程序判断其本身是否会停机并做出相反的行为,这时候显然不管停机问题的结果是什么都不会符合要求。所以这是一个不可解的问题。

2015年10月24日 (六) 07:42的版本

停机问题(Halting Problem)是1936年图灵在其著名论文“论可计算数及其在判定问题上的应用”中提出,并用形式化方法给予证明的一个不可计算问题。

基本概念

停机问题(halting problem)是目前逻辑学的焦点,也是第三次数学危机的解决方案。其本质问题是: 给定一个图灵机 T,和一个任意语言集合 S, 是否 T 会最终停机于每一个s∈S。其意义相同于可确定语言。显然任意有限 S 是可判定性的,可列的(countable) S 也是可停机的。

通俗的说,停机问题就是判断任意一个程序是否会在有限的时间之内结束运行的问题。如果这个问题可以在有限的时间之内解决,则有一个程序判断其本身是否会停机并做出相反的行为,这时候显然不管停机问题的结果是什么都不会符合要求。所以这是一个不可解的问题。

证明

首先,判定一个程序是否会停机,是指:对于其的任意一个输入,可判定其是否停机。那么假定这样的图灵机存在,设为H。其工作过程不妨设为:若对于任意一个程序M可停机则输出1,反之输出0(由于其是可判定的)。那么可以构造另一程序D,其工作过程为:以H输出为输入,若输入为1则不停机,反之停机。

由于H可判定所有程序,那么其也可判定D,若其判定D输入1时不停机,则其输出0,而由于D的定义知它是可停机的,反之亦然。故停机问题无算法解。

理发师悖论

l9世纪70年代,德国数学家康托创立了集合论,正当人们为其欢欣鼓舞时,一串串的数学悖论却冒了出来。其中,1903年的“理发师悖论”影响最大,其内容是一个理发师的招牌上写着:“城里所有不自己刮脸的男人都由我给他们刮脸,我也只给这些人刮脸。”

问题是:谁给这位理发师刮脸呢?如果他自己刮脸,那他就属于自己刮脸的那类人。但是,他的招牌说明他不给这类人刮脸,因此他不能自己来刮。如果另外一个人来给他刮脸,那他就是不自己刮脸的人。但是,他的招牌说他要给所有这类人刮脸。因此,其他任何人也不能给他刮脸。

理发师悖论的逻辑表述是:考察集合A={城里所有的男人},R={(a, b) | a给b刮脸},则R是集合A上的一个二元关系,理发师要刮脸的对象是D={a : a ∉ A且(a, a) ∈ R}。现在的问题是,理发师是否属于D?也就是D ∈ {Ra | a∉A}! 

计算理论中一个基本而重要的问题就是能否判断一个图灵机在一个给定串上的运行结果。即:ATM={<M, ω> | M是一个图灵机,M接受ω} 是否是可判定的。这个问题的实际含义就是能否编一个程序用于检验一个系统的可靠性。这个问题的回答非常出人预料,竟然是否定的,即ATM是不可判定的。其证明方法正好是借用了对角化原理。实际上,假定ATM是可判定的,并且判定它的机器为H。利用这个H来构造一个新机器D:

D=“

l 对于给定的图灵机M,将其编码为<M>

2 在输入<M, <M>>上运行H

3 输出与H相反的结论,即如果H接受,就拒绝;如果H拒绝,就接受

简单表述就是:

RTENOTITLE

当M换成D,就发现了矛盾。此矛盾说明ATM是不可判定的。注意,这里D的定义又是一个理发师!