精华内容
下载资源
问答
  • 图灵机不可判定问题

    千次阅读 2013-11-03 12:26:39
    图灵机简介  图灵机(Turing Machine)有有限个状态。其中一个状态是开始状态。这些状态的一个子集是接受状态,还有一个子集是拒绝状态。接受状态子集和拒绝状态子集不相交(不能有一个状态既是接受状态,也是...
    一. 图灵机简介
           图灵机(Turing Machine)有有限个状态。其中一个状态是开始状态。这些状态的一个子集是接受状态,还有一个子集是拒绝状态。接受状态子集和拒绝状态子集不相交(不能有一个状态既是接受状态,也是拒绝状态)。

           有一个字符集Σ,图灵机以Σ上的字符串ω作为输入(ω∈Σ*,Σ*是一个集合,它的元素是:由0个或多个Σ上的字符组成的有限长度的字符串)。图灵机还有一个字符集Γ,是”带“(tape)字符集。Γ包含Σ中的所有字符,还必须有一个Σ中没有的字符,就是空白字符。图灵机的带(tape)上一开始默认都是空白字符。图灵机的带,是一个无限长的带子,分成一个个的单元格,每一个单元格上写一个字符(初始都是空白符)。图灵机有一个读写头,总是位于带的某一个单元格之上。读写头对当前的单元格进行读写。读写头可以顺着带子左右移动,但一次只能移动一个单元格。Γ就是图灵机可以向带子上写的字符的集合。

           图灵机的动作是这样的:根据当前所处的状态和当前读到的字符,在当前单元格上写下一个字符,向左或右移动一个单元格,进入另一个状态(对于这些动作的规定,就是图灵机的转移函数δ)。一开始,将输入字符串ω(ω∈Σ*)放在带子上,把图灵机的读写头对准ω的第一个字符,并让图灵机处于开始状态。然后图灵机就开始一步一步地运行:读字符、写字符、移动读写头、进入新状态,然后再重复......直到图灵机进入某一个接受状态,这时图灵机停机并接受ω。图灵机也有可能进入一个拒绝状态而停机,这种情况下图灵机拒绝ω。除了这两种情况,还有第三种情况:那就是图灵机永远不会停机。图灵机既不进入接受状态,也不进入拒接状态,而是一直运行下去。后两种情况,合称图灵机不接受ω。

           所以,对于Σ*中的一个字符串ω,这个图灵机要么接受它,要么不接受它。图灵机不接受ω,有可能是图灵机拒绝ω,也有可能图灵机不停机。一个图灵机接受的所有字符串构成的集合(是Σ*的一个子集)作为一个语言(字符串集合即为”语言“),就是这个图灵机”识别“的语言。

           有一类图灵机,它们对于任何输入字符串ω都停机(要么接受,要么拒绝。两者必居其一)。这类图灵机被称为判定器。被判定器识别的语言称作被这个判定器”判定“(这类语言称作”可判定语言“)。如果把识别一个语言作为”计算“的通用模型(这点以后说明),那么判定器就是可以明确地给出计算结果的图灵机。要么”是“,要么”不是“。

           一个图灵机的“程序”,就是固化在它的状态集以及转移函数δ中的“动作”。但也可以构建一个”通用图灵机“,它的输入字符串是一个”序列化“了的图灵机M和一个字符串ω。”通用图灵机“在字符串ω上模拟图灵机M的行为,产生和M一样的结果(接受、拒绝或不停机)。一个图灵机只有有限个状态、有穷字符集Σ和带字符集Γ,以及定义域和值域都是有穷离散集合的转移函数δ,所以只要约定好了格式,一个图灵机就可以用一个字符串来描述(序列化成了一个字符串)。”通用图灵机“有点像可存储程序的冯.诺依曼计算机。

    二. 计算、算法与图灵-邱奇论题
           你也许会觉得:图灵机是干吗使的?答案:计算。那什么是计算?图灵机干的事情就是计算。那2×3=6图灵机能算么?如果你把"aa|aaa"作为输入字符串ω提供给某个图灵机,这个图灵机停机,并在带子上留下aaaaaa。你给了它2个a和3个a,它给了你6个a,它不就是计算了2×3=6么。

           这里对”图灵机编程“不做详细介绍了。总之图灵和邱奇证明,任何有步骤的、确定的计算过程,都可以由图灵机实现。任何可执行计算的装置:算盘、珍尼纺纱机、超级计算机等等,都可以由一台图灵机模拟。也就是说:任何计算装置,都无法超过图灵机的能力。图灵机也就定义了计算和算法。

           一切计算问题都可以等价于字符串接受/不接受问题,也就是语言的识别(也许是判定)问题。也就是说一切”计算“,都可由图灵机进行。

    三. 图灵机不可判定问题
           上面说,有些语言(字符串集合)可被一个判定器(总会停机的图灵机)判定(识别)。给一个字符串ω,这个判定器得出结论:ω是否属于这个语言。这些语言是”可判定“语言。那么是否存在不可判定语言?也就是是否存在一个语言,不存在一个判定器可以判定它?答案是”是“。设想下面的语言:

           A = {(<M>,ω) | <M>是表示图灵机M的字符串,ω是一个字符串。M接受ω}

           也就是,语言A中的字符串都有两部分组成:第一部分是一个图灵机M的字符串表示<M>;第二部分是一个字符串ω。且M接受ω。

           假设语言A是可判定的,也就是存在一个判定器H。当M接受ω时,H接受(<M>,ω);当M不接受ω时,H拒绝(<M>,ω)。(注意H是一个判定器,它总会停机,接受或拒绝(<M>,ω))。那么我们对H稍加改造,将它的结果取一下反:当M接受ω时,H拒绝(<M>,ω);当M不接受ω时,H接受(<M>,ω)。这很容易,只要把H的接收状态和拒绝状态互换一下身份即可。

           然后我们可以再对H做一个变化,它的输入字符串仅仅是一个图灵机M的序列化字符串<M>,喂给这个M的输入不再是某个字符串ω,而就是字符串<M>本身。那么H的行为就变成了:输入给它一个表示某个图灵机的字符串<M>。把<M>当做给图灵机M的输入,若M接受<M>,则H拒绝<M>;若M不接受<M>,则H接受<M>。

           精彩之处到了:若把H自己的序列化字符串<H>提供给H会发生什么?当H接受<H>时,H拒绝<H>;当H不接受<H>时,H接受<H>。理发师悖论。唯一的结论只能是,H不可能存在。就是说对于语言A,不可能构造一个判定器去判定它。A是不可判定语言。不可判定语言是存在的。

      再换一种方式说一遍(不带任何符号,争取用话说明白):假如存在一个判定器(还记得判定器么?就是总会停机的图灵机,要么接受,要么拒绝,反正不会不停机),以一个图灵机的描述(也是一个字符串)和一个字符串作为输入。它可以判定这个图灵机是否接受这个字符串,也就是:这个图灵机接受这个字符串,我这个判定器就停机接受;这个图灵机不接受这个字符串,我这个判定器就停机拒绝。(注意我这个既然是判定器,它就能做到上边说的)。那么以这个判定器为基础,就可以构造另一个判定器,这个判定器只拿一个图灵机的描述(一个字符串)当输入,然后把这个描述本身当做给这个图灵机的输入,判断这个图灵机是否接受它自己的描述:它接受,我判定器就停机并接受;它不接受,我判定器就停机并拒绝。然后以这个判定器为基础,再改造一下。这次改造简单,只是把接受和拒绝反一下:判定器的输入是一个图灵机的描述(一个字符串),然后判定这个图灵机是否接受它自己的描述:它接受,我判定器就停机且接受;它不接受,我判定器就停机且拒绝。没问题吧。好!现在把我这个判定器自己的描述输入给它,它将如何?它将在自己接受自己的描述时拒绝自己的描述;在自己不接受自己的描述时接受自己的描述。悖论了!

           如果存在不可判定语言,那么必然存在不可识别语言。就是无法构造一个图灵机,接受这个语言的每一个字符串(用不着拒绝每一个不属于这个语言的字符串,因为这里说的是识别,而不是判定)。因为:如果一个语言L和它的补^L都是图灵机可识别的,那么L是可判定的。证明:设识别L的图灵机是M1,识别^L的图灵机是M2。构造图灵机M,它在字符串ω上交替地一步一步地模拟M1和M2。因为一个字符串要么属于L,要么属于^L,也就是对于一个字符串ω,要么M1进入接受状态,要么M2进入接受状态。于是M总会看到M1或M2(之一)进入接受状态。如M1进入接受状态,则M停机并接受ω;若M2进入接受状态,则M停机拒绝ω。那么M就成了语言L的一个判定器。所以如果一个语言不可判定,必然它或者它的补是不可识别的。不可识别语言是存在的。

           一个不可判定的语言,就是一个不可计算的问题。那是一个超出了计算机能力的问题,一个不能被任何有步骤的、确定性的算法所能解决的问题。那是什么样的问题?也许是女人心吧。
    展开全文
  • 图灵机停机不可判定证明

    千次阅读 2007-07-09 18:22:00
    图灵机停机不可判定证明 利用反证法 假设存在一个M(p,d)可以判定p程序对就d输入是否停机程序p如下 p(d) { 如果 M(p,d)可停机 不可停机 否则 返回停机}请判定p否可停机 如果M(p,d)可停机 根据定义是不可停机的 如果M...
    图灵机停机不可判定证明
    利用反证法
    假设存在一个M(p,d)可以判定p程序对就d输入是否停机
    程序p如下
    p(d)
    {
    如果 M(p,d)可停机 不可停机
    否则 返回停机
    }
    请判定p否可停机
    如果M(p,d)可停机 根据定义是不可停机的
    如果M(p,d)不可停机,根据定义是停机的
     
    展开全文
  • 一、丘奇-图灵论题、 二、判定性引入、 三、图灵机语言、 四、图灵机结果、 五、判定机、 五、部分函数与全部函数、 六、判定性定义、





    一、丘奇-图灵论题



    为算法提供严格的数学模型 , 除了图灵机之外 , 还有其它的 33 种数学模型 :

    可计算函数 ,数学方向 ;

    Lambda 演算 , 程序语言方向 ;

    登记计算机 ( Register Machine ) , 计算理论方向 ;


    所有的数学模型 都为算法提供了严格的数学模型 , 这些数学模型之间是相互等价的 , 这是一个论题 , 不需要证明 ;

    图灵机为算法提供了严格的数学定义 , 不需要证明 ;


    丘奇-图灵论题 : 图灵机是计算的极限 , 是算法的严格的数学定义 ;





    二、可判定性引入



    经典的计算理论有 33 个基本概念 , 算法 ( Algorithm ) , 可判定性 ( Decidability ) , 有效性 ( Efficiency ) ;

    之前讲的 都是 算法 ( Algorithm ) 范畴的 ;


    同时 希尔伯特纲领 中 , 也要求了判定算法 , 希望存在一个算法 , 帮助判定任何一个数学命题的真假 ;

    参考博客 : 【计算理论】图灵机 ( 图灵机引入 | 公理化 | 希尔伯特纲领 | 哥德尔不完备定理 | 原始递归函数 )





    三、图灵机语言



    给定一个字符串 , 将字符串写在带子上 , 让图灵机从开始状态 , 开始位置进行计算 ,

    如果在计算过程中的 某个时刻 , 图灵机进入接受状态 , 那么称 该图灵机是接受这个字符串的 ;


    将图灵机 M\rm M接受的所有字符串 w\rm w 都放在一起 , 组成一个 集合 L\rm L , 则该集合就是 图灵机 MM 的语言 ;

    使用符号化表示为 : L(M)={ w  Mw }\rm L(M) = \{ \ w \ | \ M 接受 w 字符串 \ \}


    图灵机 计算模型 , 可以转换成语言 ;





    四、图灵机结果



    图灵机在 字符串 w\rm w 上进行计算 , 可能有 33 种不同的结果 :

    ① 图灵机进入 接受状态 , 接受该字符串

    ② 图灵机进入 拒绝状态 , 不接受该字符串

    ③ 图灵机进入 Loop\rm Loop 不停机状态 , 出现循环


    停机问题 , 在计算机科学中很重要 , 尽量避免出现 Loop 不停机状态 ;





    五、判定机



    简化图灵机 , 只研究特殊图灵机 , 该 特殊图灵机 在所有的字符串上 , 都会停机 , 任意给一个字符串 , 图灵机在该字符串上进行计算 , 要么进入接受状态 , 要么进入拒绝状态 ;

    这种特殊的图灵机 , 被称为 “判定机” ;





    五、部分函数与全部函数



    部分函数 : 任意给定一个图灵机 , 对应一个 部分函数 , 给这个函数一个输入值 , 不会有结果 ; 图灵机进入 接受 / 拒绝 状态就有结果 , 进入 Loop 状态就不会有结果 ;

    全部函数 : 任意给定一个输入值 , 都有唯一的输出值与之对应 , 这是函数 ; 这种函数称为 全部函数 ;


    这里研究的特殊的图灵机 “判定机” , 判定机 只会进入 接受 / 拒绝 状态 , 因此判定机对应的是一个全部函数 ;





    六、可判定性定义



    如果一个语言是 图灵-可判定的 , 那么一定存在一个 判定机 判定该语言 ;

    展开全文
  • 一、计算模型与语言、 二、区分 可计算语言 与 可判定语言、 三、证明 语言 可计算、 四、通用 ( Universal ) 任务图灵机 与 特殊任务图灵





    一、计算模型与语言



    计算模型是逐步进行扩张的 :

    自动机 \to 下推自动机 ( 11 个栈 ) \to下推自动机 ( 22 个栈 ) \Leftrightarrow 图灵机


    所对应的语言也是逐步进行扩张的 :

    正则语言 \to 上下文无关语言 \to 可计算语言


    正则语言 对应的 计算模型 是 确定性有限自动机 ,

    上下文无关语言 对应的 计算模型 是 下推自动机 ,

    可计算语言 对应的 计算模型 是 图灵机 ,


    可判定语言 对应的 计算模型 是 判定机 ,

    判定机 是一种 特殊的 图灵机 , 是图灵机的子集 ;

    可判定语言 是 可计算语言 的子集 ;


    图灵机 的 可计算语言 , 是计算机科学的研究领域 ;





    二、区分 可计算语言 与 可判定语言



    找一个特例语言 , 区分 可计算语言 与 可判定语言 ;


    图灵机的可接受问题 :

    将计算问题进行形式化 , M\rm M 是图灵机 , w\rm w 是字符串 , 如果 M\rm M 图灵机 接受 w\rm w 是字符串 , 将所有的可接受的 w\rm w 是字符串放在一个集合中 , 组成的语言 称为 ATM\rm A_{TM} 语言 ;

    ATM={<M,w>Mw}\rm A_{TM} = \{ <M , w> | 图灵机 M 接受 w 字符串 \}

    ATM\rm A_{TM} 语言 称为 图灵机可接受的 ;


    ATM\rm A_{TM} 语言 可计算的 , 但 不是可判定的 ;

    该结论可以区分 可判定语言 与 可计算语言 ;





    三、证明 ATM\rm A_{TM} 语言 可计算



    证明 : ATM\rm A_{TM} 语言 可计算的 , 但 不是可判定的 ;


    证明过程 : 构造图灵机 U\rm U ,

    ① 字符串 : 给定一个输入字符串 , <M,w>\rm <M , w> , 即 在 图灵机 M\rm M 上接受的字符串 w\rm w ;

    ② 模仿 : 字符串输入到 图灵机 M\rm M 之后 , 将自己想象成 U\rm U , 模仿 图灵机 M\rm M 在 字符串 w\rm w 上进行计算 ;

    ③ 接受 / 拒绝 状态 : 如果 图灵机 M\rm M 进入接受状态 , 则 图灵机 U\rm U 也进入接受状态 , 如果图灵机 M\rm M 进入拒绝状态 , 则 图灵机 U\rm U 也进入拒绝状态 ;

    ④ Loop 循环状态 : 图灵机 M\rm Mw\rm w 字符串上计算时 , 可能有第 33 种可能性 , 即进入 Loop 循环状态 , 永不停机 ; 此时 图灵机 U\rm U 也只能进入 Loop 状态 ;


    现在 图灵机 U\rm U 模仿的是 图灵机 M\rm M 在 字符串 w\rm w 上的计算 , 图灵机 M\rm M 进入什么状态 , 图灵机 U\rm U 就进入什么状态 ;


    U\rm U 很显然是 图灵机 , 因此 ATM\rm A_{TM} 语言 对应的计算问题是可计算的 ;


    证明 ATM\rm A_{TM} 语言 不可判定 , 在下一篇博客中证明 ;





    四、通用 ( Universal ) 任务图灵机 与 特殊任务图灵机



    下面开始证明 ATM\rm A_{TM} 语言 对应的计算问题 是 不可判定的 ;


    根据 丘奇-图灵 命题 , 图灵机 等于 算法 ;

    图灵机 U\rm U = " 在输入字符串 <M,w>\rm <M , w> 上 , M\rm M 是图灵机 , w\rm w 是字符串 , 则有 ① 模拟 M\rm Mw\rm w 上进行计算 , ② 如果 M\rm M 进入接受状态 , 则 U\rm U 接受 , M\rm M 拒绝 U\rm U 拒绝 , M\rm M Loop U\rm U 也 Loop "

    上述 等号 左侧是 图灵机 U\rm U , 等号 右侧 是 算法 ;

    等号 就是 丘奇-图灵 命题 ;


    U\rm U 是通用 ( Universal ) 图灵机 ,

    ① 特殊任务图灵机 : 一般情况下 计算模型 是执行一个 特定任务 , 给定一个任务 , 给定一个输入 , 图灵机进行计算 , 然后输出结果 ;

    ② 通用任务图灵机 :

    图灵机 U\rm U 不是特殊任务图灵机 , 而是一个 一般任务图灵机 , 该图灵机可以执行各种操作 ,

    将各种图灵机 , 进行编码 , 输入到通用图灵机 U\rm U 中 , 通用图灵机 U\rm U 就会模仿 特殊图灵机 M\rm M 在字符串 w\rm w 上进行计算 ;

    通用图灵机 U\rm U 的主要任务就是 模仿所有其它 特殊图灵机 M\rm M 进行计算 ;


    计算机刚出现时 , 每个计算机只能执行特殊的任务 ,

    真正的通用任务计算机是 冯诺依曼 设计的 , 可以执行所有的计算任务 ;

    展开全文
  • 最近在读图灵的两本专著,《艾伦图灵传如谜的解谜者》《图灵的秘密》,其中图灵的秘密写得真好。从康托的集合论讲到超越数。...其中我不明白的是,为什么利用图灵机模型可以证明判定性问题不解。
  • 可判定问题

    2014-01-12 16:25:57
    定义:A={ω> | M描述一台图灵机,且M描述的机器接受ω} 我们知道这个是不可判定的。 这里表示的是: M描述一台能够识别...如果这里是所有图灵可判定语言的图灵机,那么显然有这么一个图灵机A存在。因此为可判定。
  • 一、存在性证明、 二、证明 通用任务图灵机 语言 对应的计算模型一定是 不可判定 ( 对角线法 )
  • 图灵可归约性

    2011-04-24 21:56:22
    图灵可归约性 语言B的一个谕示是一个能够报告某个串W是否为B... 语言A图灵可归约到语言B,如果A相对于B是可判定的A &lt;=T B 参考资料 [1]. Rift Platinum http://www.riftgamestore.com [2]. Rift Platinu...
  • 图灵1936年论文解读(1):计算性
  • 一、不可判定性 ( Undecidability )、 ...三、"图灵机语言是否空集问题" 不可判定、 四、"图灵机是否等价问题" 不可判定、 五、"是否存在自动机接受图灵机语言问题" 不可判定、 六、莱斯定理 ( Rice's Theorem )
  • 图灵机停机问题的不判定性

    千次阅读 2017-04-09 23:04:57
    图灵机停机问题是不可判定的,意思即是不存在一个图灵机能够判定任意图灵机对于任意输入是否停机。 为了证明这个问题的不可判定性,我们将基于莱斯定理(Rice’s Theorem)将其规约成另外的问题来判定某个图灵机是否...
  • 图灵图灵

    2014-03-30 21:38:00
    学术界公认,电子计算机的理论和模型是英国数学家图灵在1936年发表的一篇论文"论计算数及其在判定问题中的应用中奠定基础的。 数理逻辑,形式逻辑和符号逻辑 用符号和公式,公理的方法研究人的思维过程,思维...
  • 超越图灵

    2021-05-14 00:06:23
    翻译:何瑞麟1 介绍Turing[8]引入了计算机(computing machine)的概念,后来被称为TuringMachine(图灵机)。他证明了Hilbert(希尔伯特)的可判定问...
  • 图灵机简介

    2015-04-20 20:37:00
    数学是可判定的吗?也就是说,能够找到一种方法,仅仅通过机械化的计算,就能判定某个数学陈述是对是错?数学证明能否机械化? 图灵机的示例。绿点指示处为当前状态,每条规则的4项分别是:当前位置读入的字符...
  • 图灵的故事

    2012-11-23 07:40:54
    图灵的天赋在他非常年轻的时候就展露无遗, 图灵在他1936年5月28日提交的重要论文《论计算数及其在判定问题上的应用》里,对哥德尔1931年在证明和计算的限制的结果作了重新论述,他用现在叫做图灵机的简单形式...
  • 本文转自豆瓣_燃烧的影子 图灵机与计算性 ...1936年4月,图灵发表了“计算数及其在判定问题上的一个应用”的论文,形成了“图灵机”的重要思想。用反证法证明,任何计算其值的函数都存在相应的图灵机;反...
  • 图灵停机问题

    2012-10-24 19:19:54
    问题描述: 通俗的说,停机问题就是判断任意一个程序是否会在有限的时间之内结束运行的问题。如果这个问题可以在有限...这个问题实际上是问: 是否存在一台"万能的"图灵机 H, 把任意一台图灵机 M 输入给 H, 它都能判定
  • 计算的极限(二):自我指涉与不可判定Comments>> 方弦 发表于 2012-12-12 14:04| Tags 标签:原创, 图灵, 数学, 计算的极限 计算无处不在。 走进一个机房,在服务器排成的一道道墙之间,...
  • 计算机科学之父--图灵

    千次阅读 2020-07-06 19:51:06
    计算机科学之父艾伦·麦席森·图灵个人简介图灵人物生平主要成就计算性理论判定问题电子计算机人工智能数理生物学图灵试验人物评价主要荣誉亲属成员后世纪念图灵奖首相致歉女王赦免英国情报机构道歉百年纪念英国50...
  • 图灵机是一个计算模型,最早用来解决判定一个问题到底可不解,那么它是如何判定的呢? 在本篇文章开始之前,我们先来看一段视频: https://www.zhihu.com/zvideo/1287337736785944576 图灵机的构成 为了方便讲述...
  • 图灵完备的机器可以解决所有解问题,亦即任何图灵完备的机器逻辑上都是等价的。 那么什么属于不解的问题呢?这里我们引出一个问题:不存在这样的一个程序,它可以判定任意程序是否会结束执行(停机问题)。  ...
  • 文章目录计算希尔伯特问题哥德尔定理图灵和不计算性定义为图灵机的明确程序通用图灵图灵判定问题的解决 计算 在普通人眼里,计算就是计算机做的事情,电子表格、文档处理、电子邮件等等。 不过如果你读复杂...
  • 该书介绍了图灵的论文《论计算数及其在判定上的应用》, 其指出: 一个拥有铅笔, 纸和一串明确指令的人类计算者, 可以被看做是一种图灵机. 那么图灵机是什么呢? 是图灵为了描述计算数而引出的一个虚构的可以做...
  • 如果一个语言能被某一图灵机识别,则称该语言是图灵可识别的。 在输入上运行一个TM时,可能产生三种结果:接受,拒绝或循环(这里的循环仅仅指机器不停机) 对所有输入都停机的图灵机,即永不循环,这种机器叫判定...
  • 上一讲我们知道了图灵机在历史上出现的原因,它是一个计算模型,用来判定一个问题到底可不解,那么它是如何判定的呢? 在本篇文章开始之前,我们先来看一段视频: 视频来源:YouTube(经下载后上传到腾讯视频) ...
  • 关于TCS中的图灵机模型和神谕机

    千次阅读 2015-05-19 16:31:52
    对于普通的图灵机而言,停机问题是不可判定的,这早已被证明。而图灵发现,即使将证明中的所有“图灵机”三个字都换成“带有‘数论问题’谕示的谕示机”,其他部分一字不易,证明依然成立!也就是说,就像普通图灵机...
  • 上一讲我们知道了图灵机在历史上出现的原因,它是一个计算模型,用来判定一个问题到底可不解,那么它是如何判定的呢? 在本篇文章开始之前,我们先来看一段视频: https://www.youtube.com/watch?v=E3keLeMwfHY ...
  • 1.1936 - On Computable Numbers, with an Application to the Entscheidungsproblem(论计算数在判定问题中的应用) 2. 1950 - Computing Machinery and Intelligence(计算机器与智能,也译作:机器能思考么?)...
  • 图灵机是迄今为止计算能力最强的计算模型,在理论层面上有着其他模型不可替代的重要作用,它深刻地刻画了物理世界的可识别与可判定2个重要的概念。文章给出了这2种计算模型的一些基本概念、结论以及解决问题的主要...

空空如也

空空如也

1 2 3 4 5
收藏数 86
精华内容 34
关键字:

图灵可判定