不可解问题(Undecidable Decision Problem)

    看黑书介绍NP的时候有一个“不可解问题”,非常不可思议,费劲周折在网上查到了些英文资料,搞明白了,非常有意思,在这里说一下。
    不可解问题(Undecidable Decision Problem)指的是这样一种问题:他无论如何也不可能有一个正确的算法来解决。虽然不可思议,但这种问题被证明确实是存在的。图灵在1936年(那时还没电脑,我们的父亲是在没有设备支持的纯理论基础上提出来的,致敬)提出了第一个不可解问题的实例:The Halting Problem。
    The Halting Problem是问,输入一段程序代码和一个针对此程序的输入,能否编程判断运行这个程序后程序是否会终止。
    这个问题的答案是否定的。也就是说,不可能有一种算法可以正确判断一个指定的程序运行后,给予指定的输入,程序最后出不出得来。换句话说,The Halting Problem是一个不可解问题。
    虽然这感觉似乎不可能,但在严格的证明下谁也无法发言反对。
    证明过程非常简单,假设The Halting Problem是有解的,并且已经用程序实现了,那么我们只需要再编写一个程序Program Bug,就会发现存在矛盾。
    反证:既然解决The Halting Problem的算法已经实现了,那么我们一定能定义一个函数
Function Halting(a,b:input_type):boolean;
    其中,a是读入的程序源码,b是输入数据。这个函数的功能就是返回对于指定的程序源码和输入数据,程序是否能顺利退出。
    下面编写一个程序:
Program Bug;
var
    code:input_type;
begin
   get(code);   //读入code
   if halting(code,code) then repeat until false
      else halt;
end.

    好,现在运行Bug这个程序,并且输入Bug这个程序本身的代码。这样,halting(code,code)其实质就是在判断这个Bug程序本身了。如果The Halting Problem认为Bug程序会正常退出,那么就让程序进入一个死循环,否则立即退出程序。矛盾产生。
    //简直是在挑战表达力极限
    //做人要厚道,转帖请注明出处

46 条评论

  • flyingforever

    您的表达还是很清楚的嘛
    那个反证法太美妙了…

  • yiyi

    最后一段懂了,很不错的反证…[GoodLuck]

  • yiyi

    图灵为何不喜欢MM呢?[tea]

  • OrangeCLK

    证法的确相当经典,ps这题作为NOIP2007提高组初赛题考了。

  • fxnew

    能否等价为:
    输入一段代码A和一个针对A的输入a,能否编程B判断A(a)是否是死循环。

    回复:对

  • xcjzj

    终于有个上网的机会,来看看你的地盘。
    自我感觉这是个在你给出的BUG程序下会成为悖论的问题。简称program bug 为悖论程序,呵呵。
    学数学蛮好玩。我们最近教到叉乘了,还记得在bsy的时候,你来给我们讲了叉乘,那天晚上我在寝室熬夜整理笔记到将近两点。咳……信息竞赛的任何一个回忆的片段总能给我很深的感慨,不知道你是不是呢?

  • Princess

    [loo]

    那啥。。。我一直想知道。。。黑书是什么?

    回复:算法艺术与信息学竞赛

  • 前尘◎如梦

    我觉得关于问题的表述
    应该换成一种更清晰的不易让人误解的方式
    比如:能否存在一种算法,对任意一个给定程序A,以及任意一个针对A的输入,判断出A是否能够终止。

  • 凌晨海风

    我不认同这个反证法,这个证明带有自指性(读入自己这段程序)。就像集合论中的某些悖论一样,钻了定义的空子。

  • iveney

    @凌晨海风
    自指性很正常吧。
    如果不认同这个反证法,那可以看看哥德尔不完备性定理以及康托对角线删除方法的证明。

  • Little Jerry

    啊。。。我想问。。。你这些东西是在哪找的啊。。。好强啊

  • axgle

    类比一下,假设存在上帝,而你现在在梦中。
    如果你认为你马上会从梦中醒来,那么上帝就不让你醒来,所以你的‘认为’是错的;如果你认为你不会醒来,那么上帝就让你醒来,所以你的‘认为’依然是错的。因此,无论你怎么认为,上帝都可以判决你的认为是错的。
    停机问题于此类似,只不过这里的上帝是程序员,代码是梦中的人。可见停机问题是荒谬的

  • axgle

    停机问题与表达式(符号)的任意性:
    我把(code,表达式,符号,字母)暂时视为通一个东西。
    我们可以任意的输入一段代码,例如“Program Bug”,又比如:

    a=”a就是非a”

    假定这里的a是同一个东西,那么就会出现‘悖论’:a为真,则a为假;a为假,则a为真。为什么会这样呢?因为它给出的表达式“a就是非a”本身就违反了矛盾律。

  • axgle

    我说的这句话是假话;语言结构:
    假设“这句话”=a
    那么 a=”a是假话”,即a=”a并非a”

  • 北极冰仔

    反证法确实厉害……

  • g

    运行BUG程序,会在无限时间之后返回一个类似:此题有限时间内不可解 的东西

  • 光荣与梦想

    悖论就是在没有限制条件下自相矛盾的事,如同理发师说“我将给所有不能自己剪头发的人理发”一样,只有对象是理发师自己时才会出现错误。只要加上一条说明“除了自己以外”就没有问题了。
    那么这个证明会不会也是这样,用反证法来证明只是一个对于本身而言的逻辑上的错误,只要在使用Halting函数时避免递归调用,就不会有矛盾产生。
    ¿Sí?

  • sed

    地下室说的比较好理解。

  • lzb198259

    不明白最后的自我验证程序的原理,为什么是不停机时推出repeat,停机时继续执行? 既然是判断是否停机,那么当停机时(为true时)就推出并返回真值不就好了吗?

  • 东纹玖

    概念的错误,怎么不可解,只不过形式是无穷嵌套,是问题本身的平凡解,不是不可解,是偷换概念,显然问题的非平凡解才是要考虑的,我觉得大家对语言的使用带有歧义性。

  • blade

    和集合论的不存在一个包含所有集合的集合证明有点像

  • victor_chia

    无非是说,“无所不能”的上帝却不能创造出一个连他也搬不动的石头来罢了

  • 池塘仙人

    楼层: 25楼 | 2010-08-12 17:51 | victor_chia 说:
    无非是说,“无所不能”的上帝却不能创造出一个连他也搬不动的石头来罢了

    如果同意上帝无所不能,那么是否同意上帝可以是矛盾的?上帝可以是游离于人类逻辑之外的?

  • KMP

    MAIN{
    IF(PRESULT(*MAIN,0,NULL)!=LOOPEN)WHILE(1);}

  • fremn

    我也觉得,bug程序对应的输入 是什么啊?

  • pyramid1988

    传说中的自指啊,怎感觉貌似好多问题都是自指给否定了

  • himdd

    以子之矛攻子之盾。很好的矛盾啊。。

  • Alaxn

    其实,我自己在想,假如我们把这个halting probleam类比到人脑,那么会不会有什么可取之处呢,对于解决这个停机问题来讲
    也许正是因为人脑可以控制自己不去进行这个工作,把这个问题停下来,所以不会有这个奇怪的问题吧。。。表达有点奇怪。。。

  • easoncxz

    (no chinese IME at this time)
    is it basicly jsut a paradox?

  • Makeecat

    并不完全认可这个反证法。

  • fle4y

    最后BUG 可以不用输入BUG程序本身吧 可以 Bug input 也可以吧

  • WF

    典型的理发师问题,集合论里的自指。个人觉得在哲学里这就是一个判断范畴定义的问题,你在做判断前,必须指定判断的过程中不得出现判断本身,因为后者范畴大于前者。用数学语言来说这就是公设。有这个公设,哲学里的判断才存在,否则就像“我正在说的话是假话”一样出悖论。当然我们允许没有公设,非欧几何也有其意义。

  • 放屁有益健康

    首先,可定义并不就意味着一定存在!因为我们也可以定义“上帝”。实际上,塔尔斯基就是用“A=非A”来定义空集的,也即根本不存在满足“A=非A”的A!

  • 沉沦的夜

    Program Bug;
    var
    code:input_type;
    begin
    get(code); //读入code
    if halting(bug,code) then repeat until false
    else halt;
    end.

发表评论