理发师悖论

来自计算思维百科
跳转至: 导航搜索

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的定义又是一个理发师!