人工智能通识-科普-图灵机之可计算性
所有数学问题都可以用计算机来解决吗？ 如 上一篇繁忙的海狸Busy beaver 中所展示的，海狸是否会陷入无法停机的无限循环？这个看似简单的数学问题就无法完全用计算机来彻底解决，或者说它是不可计算的。 可计算性是指某个数学问题是否可以用计算机 在有限步骤内彻底解决 。 首先必须是数学问题，而不能是 给我做个汉堡包 这种需要真实的实体变化的问题。 其次必须是有限步骤，如果这个问题的算法远远超过计算机目前可能拥有的计算能力，那么也应该视为不可计算的。 研究问题的可计算性质可以避免浪费时间在无底的坑里面做无意挣扎。 可计算性是针对问题而言的，问题又主要是以下两类： 另外还有 搜索问题Search Problem (在对象Y中是否能够找到符合要求的结构x)和 最优化问题Optimization Problem (多个解决方案中哪一个更优）。 图灵机是一种抽象的计算模型，理论上可以实现无限多种算法，类似的计算模型（功能模型Functional models）还有以下几个，他们都被认为是 图灵等价或图灵完整Turing completeness 的： 如上所示，递归理论起源于20世纪30年代，由库尔特·哥德尔KurtGödel，阿隆佐·邱奇Alonzo Church，罗莎·培特RózsaPéter，阿兰·图灵Alan Turing，斯蒂芬·克莱尼Stephen Kleene和埃米尔·珀斯特Emil Post等人提出。 早在1936年就邱奇和图灵就受到哥德尔的不完备性定理的启发，算法程序不可能正确的判断任意数学问题的真假。后来这个理论就被称为Church-Turing论文，定义了可计算概念的含义：可由算法计算的函数都是可计算函数。 可计算性的提出，也意味着科学家们对不可计算问题的认可，证明了数学中确实存在无法有效解决的问题。 此外还有描述可计算程度的相对可计算性Relative computability 和图灵度Turing degrees。 END
图灵机模型由哪几部分组成？
该机器由以下几个部分组成：1.一条无限长的纸带 TAPE。纸带被划分为一个接一个的小格子，每个格子上包含一个来自有限字母表的符号，字母表中有一个特殊的符号 表示空白。纸带上的格子从左到右依此被编号为 0,1,2,... ，纸带的右端可以无限伸展。2.一个读写头 HEAD。该读写头可以在纸带上左右移动，它能读出当前所指的格子上的符号，并能改变当前格子上的符号。3.一套控制规则 TABLE。它根据当前机器所处的状态以及当前读写头所指的格子上的符号来确定读写头下一步的动作，并改变状态寄存器的值，令机器进入一个新的状态。4.一个状态寄存器。它用来保存图灵机当前所处的状态。图灵机的所有可能状态的数目是有限的，并且有一个特殊的状态，称为停机状态。扩展资料图灵机有很多变种，但可以证明这些变种的计算能力都是等价的，即它们识别同样的语言类，而且图灵机是一个抽象的机器，它有一条无限长的纸带，纸带分成了一个一个的小方格，每个方格有不同的颜色。
