美文网首页理科生的果壳有意思的文章
类比停机判定机和超现实数的无限

类比停机判定机和超现实数的无限

作者: LostAbaddon | 来源:发表于2017-09-26 00:53 被阅读98次

    停机判定机和超现实数的无限之间的关系可以这么给出:

    我们将符号“>”定义为“可判定其是否停机”,将符号“<”定义为“可被其判定是否停机”,空集<|>定义为空字符串构成的图灵机,且定义为肯定停机。
    那么,元素a定义为<A|B>的意思,就是a可以判定集合A中的图灵机是否停机,且不可判定集合B中的图灵机是否停机,即x>A且!(x>B),记为a=<A|B>。

    现在我们定义T为所有图灵机构成的集合,并定义元素w=<T|>,顾名思义就是w可判定T中任意元素(任意图灵机)但没有元素被指定为可判定w是否停机。前一个条件是停机判定机的定义,后一个条件则源自于那个古老的停机不可判定证明。因此,w=<T|>就是停机判定机。

    显然,我们将T改定义为自然数集N或者实数集R,>重新定义为大于,<重新定义为小于,那么<A|B>定义的就是超现实数,而<T|>就是超现实数中第一个表征无限的符号。
    简而言之,(图灵机集, 可判定证明, 可判定证明)与(实数, 大于, 小于)可以被相同的形式符号系统(T, >, <)表达,这两个系统是同构的。

    因此,停机判定机是比图灵机更“大”的无限机中的一个表征符号——未必是第一个,因为同样的手法我们可以证明K氏长度计算机也是这么一类比图灵机更“大”的无限机中的一个表征符号。

    当然,上述类比中缺少的一环,是给出超现实数中加法和乘法在超现机中的表达,当然,这个对于我们这里所用的类比来说,并不重要,嘿嘿。

    相关文章

      网友评论

      • XyanXcllet:这不就像图灵度么?经过一次图灵跳跃等到图灵停机判定谕示机。它与图灵机之间又夹着无穷多个介于二者之间而计算能力又互不相等的模型。?
      • 十酒三:超现实数是hyperreal么?
        LostAbaddon: @十酒三 直接后面写空也可以,因为可能存在也不能被某些非图灵机判定的情况。
        超现实数里空集很有用很赖皮……
        十酒三:@塔塔酱 那应该是写成<T|T>吧。可判定T中元素停机但不能被T中元素判定。
        LostAbaddon: @十酒三 不是,那个是超实数,非标里面的。这个是surreal,生命游戏作者Conway提出的。

      本文标题:类比停机判定机和超现实数的无限

      本文链接:https://www.haomeiwen.com/subject/topjextx.html