精华内容
下载资源
问答
  • 图灵机简介

    万次阅读 2017-10-19 23:57:05
    今天计算机病毒课上老师给我们介绍了一下图灵机。以前一直有听说过图灵机,今天简单地了解了一下图灵机,写下一些学习过程中的收获。图灵机是由图灵大神由1936年提出的一种确定的抽象计算模型,据说它可以被看做是...

    今天计算机病毒课上老师给我们介绍了一下图灵机。以前一直有听说过图灵机,今天简单地了解了一下图灵机,写下一些学习过程中的收获。

    图灵机是由图灵大神由1936年提出的一种确定的抽象计算模型,据说它可以被看做是终极强大的逻辑机器。

    图灵的基本思想是用机器来模拟人们用纸笔进行数学运算的过程,他把这样的过程看作下列两种简单的动作:
    • 在纸上写上或擦除某个符号;
    • 把注意力从纸的一个位置移动到另一个位置;

    而在每个阶段,人要决定下一步的动作,依赖于(a)此人当前所关注的纸上某个位置的符号和(b)此人当前思维的状态。

    为了模拟人的这种运算过程,图灵构造出一台假想的机器,该机器由以下几个部分组成:

    1. 一条无限长的纸带TAPE。纸带被划分为一个接一个的小格子,每个格子上包含一个来自有限字母表的符号,字母表中有一个特殊的符号表示空白。纸带上的格子从左到右依次被编号为0, 1, 2, …,纸带的右端可以无限伸展。
    2. 一个读写头HEAD。该读写头可以在纸带上左右移动,它能读出当前所指的格子上的符号,并能改变当前格子上的符号。

    3. 一套控制规则TABLE。它根据当前机器所处的状态以及当前读写头所指的格子上的符号来确定读写头下一步的动作,并改变状态寄存器的值,令机器进入一个新的状态。

    4. 一个状态寄存器。它用来保存图灵机当前所处的状态。图灵机的所有可能状态的数目是有限的,并且有一个特殊的状态,称为停机状态。
      注意这个机器的每一部分都是有限的,但它有一个潜在的无限长的纸带,因此这种机器只是一个理想的设备。图灵认为这样的一台机器就能模拟人类所能进行的任何计算过程。

    在最初的设计中图灵机中是采用一种带(tape)的东西作为临时存储,这种带子无限长。带可以被划分成一个个的单元,每个单位只包含一个符号。带子的各个单位可以被读写头读写,这个读写头可以在带子上左右移动,但是每次只能读写一个符号。

    我们可以把这个带子和读写头的关系跟初中使用过的复读机的磁带、磁头想类比。一般它直观看起来像是这个样子:

    这里写图片描述

    表示当前状态为q0,读写头的字符为a时,状态转移的时候会把这个读写头所指的字符改为b,然后读写头先左移动一个单位,状态由q0变成q1.

    通常图灵机以一个给定的初始状态和带上的信息开始,然后在状态函数的指导下由一个状态转移到另外一个状态。最后图灵机将处于停机(halt state)状态。当图灵机到达一个状态函数没有定义的输入时,图灵机将会停止。另外,我们假定对于任意的状态都没有定义其转移函数,图灵机到达状态的时候都会停机。

    图灵论题:

    任何在算法上可计算的问题同样可由图灵机计算;
    任何无法由图灵机计算的问题都不可能找到解决的算法。

    展开全文
  • 图灵机与计算理论

    千次阅读 2018-06-18 10:38:45
    图灵机和计算理论是人工智能乃至整个计算机科学的理论基础,邱奇-图灵论题告诉我们一切可计算过程都可以图灵机模拟图灵机 图灵机,又称图灵计算、图灵计算机,是由数学家艾伦·麦席森·图灵(1912~1954)...

    前言

    图灵机和计算理论是人工智能乃至整个计算机科学的理论基础,邱奇-图灵论题告诉我们一切可计算过程都可以用图灵机模拟。

    图灵机

    图灵机,又称图灵计算、图灵计算机,是由数学家艾伦·麦席森·图灵(1912~1954)提出的一种抽象计算模型,即将人们使用纸笔进行数学运算的过程进行抽象,由一个虚拟的机器替代人们进行数学运算。

    这里写图片描述

    图灵机指一个抽象的机器,它有一条无限长的纸带,纸带分成了一个一个的小方格,每个方格有不同的颜色。有一个机器头在纸带上移来移去。机器头有一组内部状态,还有一些固定的程序。在每个时刻,机器头都要从当前纸带上读入一个方格信息,然后结合自己的内部状态查找程序表,根据程序输出信息到纸带方格上,并转换自己的内部状态,然后进行移动。

    每一个会决策、会思考的人都可以被抽象地看成一台图灵机。该模型主要有四要素:输入集合、输出集合、内部状态和固定的程序。如果把人进行抽象,那么输入集合就是所处环境中所看到、听到、闻到、感觉到的一切;输出集合就是人的每一言每一行,还有表情动作;内部状态集合则可以把神经细胞的状态组合看成一个内部状态,所有可能的状态集合将是天文数字。

    人有记忆,图灵机有没有?有,它有了内部状态就可以看成有记忆,内部状态会记录所经历过的世界。

    很多现象似乎都能被图灵机包括,如人了IDE情绪和情感,可以看成某种内部状态,心情好的情绪下,输入和输出是一套规则,而心情不好的情况下,输入输出又是另外一种规则。

    无论是神经元传递信息、变化状态的规律都是固定的,可以被程序化。那么头脑作为神经元的整体,它的运作也比如遵循固定的规则,即程序。正如图灵相信的,人脑也不会超越图灵机模型。

    关于图灵机的学习问题,看似图灵机不包括学习,因为学习就意味着程序的改变,而图灵机不能在运行过程中改变自己的程序。很有可能一个图灵机的规则没有改变,只不过激活了它的某些内部状态,因为发生了本质的变化,尽管给它相同的输入,它却有完全不同的输出,这样看起来似乎它会学习了,虽然图灵机的程序一点都没变。

    通用图灵机存在吗

    是否存在一台万能图灵机能模拟其他所有图灵机?这台万能图灵机就是通用图灵机,把输入x和图灵机m信息都一起输入到通用图灵机,就能计算出一个结果o,这样便可以模拟任何一台图灵机。

    图灵机m信息其实就是编码,通过编码可以将事物进行编号,将所有图灵机进行编码后每个图灵机就有了描述信息,如果某台图灵机的编码为m,输入为x,则将两者合并一起输入到万能图灵机中,计算得到结果。

    停机问题

    尽管图灵机很强大,但它也有解决不了的问题,比如停机问题。通俗地讲,停机问题就是判断任意一个程序是否能在有限的时间之内结束运行的问题。该问题等价于如下的判定问题:是否存在一个程序P,对于任意输入的程序w,能够判断w会在有限时间内结束或者死循环。

    1936年图灵已经证明了这样的程序是不存在的。

    从停机问题中可以看到的确存在人类能构造出来而图灵机解决不了的问题,也就是计算机不能解决的问题,这类问题是不可计算的。停机问题揭示了宇宙中的某种共性,所有计算机解决不了的问题本质上讲都和图灵停机问题是计算等价的。相似问题还包括是否存在一个程序能检测所有程序会不会出错。

    停机问题也喝复杂系统的不可预测性有关,存不存在一个程序接收某个复杂系统的规则,然后输出结果?答案是不可能。所以得到一个结论是我们要想弄清楚某个复杂系统运行结果,唯一的办法就是人为去编程实际运行后才能得到结果。这也说明了某些事机器做不了而人类能实现。

    超越图灵计算理论

    一个固定的程序不可能超越图灵计算理论的限制,但如果一个程序能在每时每刻都变化使之不再是原来的自己,那么就可以超越图灵计算理论。就好比人类每时每刻都经过细胞更新使得不再是原来的自己,所以人类超越图灵计算理论。这也就是说,人们没办法通过编写一个固定的程序来实现大脑功能。要实现真正的人工智能,就需要一个能不断改变自己的程序,而且这种改变也不是一个固定的程序。

    ————-推荐阅读————

    我的2017文章汇总——机器学习篇

    我的2017文章汇总——Java及中间件

    我的2017文章汇总——深度学习篇

    我的2017文章汇总——JDK源码篇

    我的2017文章汇总——自然语言处理篇

    我的2017文章汇总——Java并发篇


    跟我交流,向我提问:

    这里写图片描述

    公众号的菜单已分为“读书总结”、“分布式”、“机器学习”、“深度学习”、“NLP”、“Java深度”、“Java并发核心”、“JDK源码”、“Tomcat内核”等,可能有一款适合你的胃口。

    为什么写《Tomcat内核设计剖析》

    欢迎关注:

    这里写图片描述

    展开全文
  • 图灵机的组成 网上有一张经典的图片来表达图灵机的构成,图如下: 这张图片什么意思?这么一个简单的机器/装置怎么会所有电子计算机的理论模型? 图灵的基本思想是用机器来模拟人们用纸笔进行数学运算的过程,它...

    图灵机的组成

    网上有一张经典的图片来表达图灵机的构成,图如下:

    在这里插入图片描述

    这张图片什么意思?这么一个简单的机器/装置怎么会所有电子计算机的理论模型?

    图灵的基本思想是用机器来模拟人们用纸笔进行数学运算的过程,它运算过程看作下列两种简单的动作:

    • 在纸上写上或擦除某个符号;
    • 把注意力从纸的一个位置移动到另一个位置;
      图灵机把复杂的过程抽象成了上述两个动作:读写移动

    逻辑结构上图灵机有四个部分组成:

    1. 一个无限长的存储带,带子有一个个连续的存储格子组成,每个格子可以存储一个数字或符号
    2. 一个读写头,读写头可以在存储带上左右移动,并可以读、修改存储格上的数字或符号
    3. 内部状态存储器,该存储器可以记录图灵机的当前状态,并且有一种特殊状态为停机状态
    4. 控制程序指令,指令可以根据当前状态以及当前读写头所指的格子上的符号来确定读写头下一步的动作(左移还是右移),并改变状态存储器的值,令机器进入一个新的状态或保持状态不变。

    大家可以理解一下为什么图灵机要由上面四部分组成。

    当然这些只是理想的图灵机,因为现实中不存在无限长的存储带。

    展开全文
  • S 75-80或https://www.researchgate.net/publication/254389437_ACCELERATION_TECHNIQUES_FOR_BUSY_BEAVER_CANDIDATES 与使用基本图灵机相比,使用宏机可以显着提高仿真性能(但是不能保证加速)。 运行...
  • 微型扩展模拟计算机(uEAC)是受Rubel EAC模型启发的电子实现。 在这项研究中,提出了一个完全连接... 然后,通过证明即使在存在有限噪声的情况下,也可以使用uEAC可计算的功能对图灵机M进行仿真,从而研究其计算能力。
  • 接下来,文章介绍了跟图灵机有关的概念:什么是模拟,什么是“万能计算机”等等;最后是关于图灵停机问题的探讨,我个人认为很有可能未来对科学的重大突破都来源于对图灵停机问题的深入理解。在行文过程中,我除了用...
  • 图灵完备 – 维基百科 ...还有一个相关概念是图灵等价 – 如果P可以模拟Q并且Q可以模拟P,则两台计算机P和Q称为等效计算机。 邱奇-图灵论题认为任可以通过算法计算其值的函数都可以由图灵机计算,因此,如果任

    图灵完备 – 维基百科

    在可计算性理论里,如果一系列操作数据的规则(如指令集、编程语言、细胞自动机)可以用来模拟任何图灵机,那么它是图灵完备的。这意味着这个系统也可以识别其他数据处理规则集,图灵完备性被用作表达这种数据处理规则集的一种属性。如今,几乎所有编程语言都是具有图灵完备性的。这个词以引入图灵机概念的数学家艾伦·图灵命名。

    还有一个相关概念是图灵等价 – 如果P可以模拟Q并且Q可以模拟P,则两台计算机P和Q称为等效计算机。 邱奇-图灵论题认为任可以通过算法计算其值的函数都可以由图灵机计算,因此,如果任何真实世界的计算机都可以模拟图灵机,则其对图灵机是图灵等价的。 通用图灵机可用于模拟任何图灵机,且可以扩展现实世界计算机的计算方面。[NB 1]

    如果某物是图灵完备的,则它可以用于模拟某些图灵完备的系统。例如,一个指令式编程具有条件表达式(例如,“ if”和“ goto”语句,或者“branch if zero”的指令;请参见单一指令计算机)并且具有更改任意指令的能力,则他为图灵完备的。当然,任何物理系统都不可能拥有无限的内存。但如果忽略了有限内存的限制,则大多数编程语言都将是图灵完备的。

    1. 什么是图灵机

    图灵机的结构包括以下几个部分:

    1. 一条无限长的纸带(tape),纸带被分成一个个相邻的格子(square),每个格子都可以写上至多一个字符(symbol)。
    2. 一个字符表(alphabet),即字符的集合,它包含纸带上可能出现的所有字符。其中包含一个特殊的空白字符(blank),意思是此格子没有任何字符。
    3. 一个读写头(head),可理解为指向其中一个格子的指针。它可以读取/擦除/写入当前格子的内容,此外也可以每次向左/右移动一个格子。
    4. 一个状态寄存器(state register),它追踪着每一步运算过程中,整个机器所处的状态(运行/终止)。当这个状态从运行变为终止,则运算结束,机器停机并交回控制权。如果你了解有限状态机,它便对应着有限状态机里的状态。
    5. 一个有限的指令集(instructions table),它记录着读写头在特定情况下应该执行的行为。可以想象读写头随身有一本操作指南,里面记录着很多条类似于“当你身处编号53的格子并看到其内容为0时,擦除,改写为1,并向右移一格。此外,令下一状态为运行。”这样的命令。其实某种意义上,这个指令集就对应着程序员所写下的程序了。


    在计算开始前,纸带可以是完全空白,也可以在某些格子里预先就有写上部分字符作为输入。运算开始时,读写头从某一位置开始,严格按照此刻的配置(configuration),即:

    • 当前所处位置
    • 当前格子内容

    来一步步的对照着指令集去进行操作,直到状态变为停止,运算结束。而后纸带上留下的信息,即字符的序列(比如类似“…011001…”)便作为输出,由人来解码为自然语言。

    要重申一下,以上只是图灵机模型的内容,而非具体的实现。所谓的纸带和读写头都只是图灵提出的抽象概念。为便于理解打一个比方。算盘虽然不是图灵机(因为它没有无限长的纸带,即无限的存储空间),但它的行为与图灵机一致。每一串算珠都是纸带上的一格,一串算珠上展示的数字便记录着当前格中的字符(可以是空白,可以是 12345 )。人类的手即是读写头,可以更改每串算珠的状态。算盘的运行遵循人脑中的算法,当算法结束,算盘停机。

    2. 图灵机可以解决什么问题

    在计算机领域,或者说自动机领域,我们研究的一切问题都是计算问题(Computational Problem)。它泛指一切与计算相关的问题。

    A computational problem is a mathematical object representing a collection of questions that computers might be able to solve.

    计算问题的一些举例:

    1. 给定一个正整数 n,判断它是否是质数
    2. 给定一个 01 序列,把它们按位取反
    3. 给定一个字符串,判断某个字符是否存在,及查找存在位置
    4. 给定一个逻辑蕴含的命题,求它的逆否命题

    非计算问题的例子:

    1. 今晚吃什么
    2. 为什么太阳从东边升起

    计算问题有的可以解决,有的不可解决。这就引出了计算问题的可计算性(Computability)。它可以被理解为“是否存在一个算法,能解决在任何输入下的此计算问题”。如上面的问题 1,我们当然可以找到一个算法来解决判断任意正整数 n 是否为质数的问题(比如从2遍历到 n-1,看 n 是否可以整除它)。所以,问题 1 就是可计算的。

    也有一些不可计算的计算问题,比如著名的停机问题(Halting Problem)。它的表述是这样的:给定一段程序的描述和该程序的一个有效输入,运行此程序,那么程序最终是会终止,还是会死循环下去?

    Halting Problem: given the description of an arbitrary program and a finite input, decide whether the program finishes running or will run forever.

    这个问题很绕人,有点像那个著名的理发师悖论,但它确实是一个计算问题。更具体的,它是一个不可判定问题(Undecidable Problem)。即不存在一个通用算法,可以在任意输入下解决此问题。图灵在文章里很优雅的用反证法推翻了假设“假设有这么一个算法可以解决任何停机问题”,从而证明了这样的算法并不存在。具体证明过程网上的资料非常丰富,我就不再花篇幅了。

    回到这一节的主题。简而言之,对于一个问题,对于任意输入,只要人类可以保证算出结果(不管花多少时间),那么图灵机就可以保证算出结果(不管花多少时间)。

    参考

    https://zh.wikipedia.org/wiki/%E5%9C%96%E9%9D%88%E5%AE%8C%E5%82%99%E6%80%A7

    https://www.zhihu.com/question/20115374

    展开全文
  • 在可计算性理论(computability theory)中,图灵等价指的是:对于两个计算机A和B,如果A可以模拟B,B可以模拟A,就称他们是图灵等价的。 根据“丘奇-图灵”理论,图灵机是表达能力最强大的计算系统,对现实世界中的...
  • 模拟冯.诺依曼计算机

    千次阅读 2009-10-03 00:26:00
    (值此中秋佳节之际,祝愿天下所有为理想奋斗着、努力着、梦想着的人心想事成)道指令不但可以模拟图灵机、元胞自动机、神经元、基因等的工作过程,还可以模拟冯.诺依曼计算机,现在要利用道指令编制模拟冯.诺依曼...
  • 图灵机是为了用机器模拟人的运算过程而实现的,当图灵机从纸带(tape)上读取一个空格的信息,它就会根据控制器当前的状态和控制规则(控制规则由控制器中的program提供),改变控制器的当前状态,应该也可以改变...
  • 计算机导论课程小结2

    2019-11-24 00:05:57
    图灵机在理论上能够模拟现代数字计算机的一切运算,可以视为现代数字计算机的数学模型,是一种抽象的计算模型。图灵机能表示算法、程序和符号行的变换,因此成为计算机的数学模型,也可用做控制算法的数学模型。因此...
  • 尽管图灵机的模型非常简单,但是在理论上可以模拟现代数字计算机的一切运算,是一种抽象的计算模型。 计算机科学的定义 对于不同种类的学科形态,基本可以将他们的研究方向分为三种:理论研究,模型抽象,工...
  • 计算机导论周总结2

    2019-11-24 23:23:54
    **计算机导论周总结2** ...图灵机在理论上能够模拟现代数字计算机的一切运算,可以视为现代数字计算机的数学模型,是一种抽象的计算模型。 二、计算机科学的定义 1.计算机科学的学科形态 计算机科学的基本思路涵...
  • 计算机科学导论

    2019-11-24 22:36:28
    图灵机模型在理论上能够模拟现代数字计算机的一切运算,可以视为现代数字计算机的数学模型,是一种抽象的计算模型。 2.计算机科学的定义 计算机科学是一个学科。计算机科学的基本思路涵盖从理论研究、模型抽象到工程...
  • 而他们往往都需要借助某些机械计算设备或模拟计算机。) 沿着时间轴我们可以大概将计算机的发展历史分为四个阶段 目录 1.机械计算设备时代 1.1机械形式计算向电子式计算转变的一些关键点 1.1.1二进制的...
  • 图灵完备:可计算任何图灵可计算问题(在可计算性理论里,如果一系列操作数据的规则(如指令集、编程语言、细胞自动机)可以用来模拟单带图灵机,那么它是图灵完备的。) 1.冯诺伊曼体系结构 M:存储器 CA:...
  • 寄存器 RodRego

    2019-09-09 21:31:21
    寄存器机(register machine)是一种类似于图灵机一样的抽象机器,是计算机模型的一种,他和其他的抽象机一样都是图灵等价的。 RodRego是哲学家丹尼尔·丹尼特和他的朋友制作的一款寄存器机模拟软件。通过编写简单的...
  • 那传说中的P、NP以及NPC问题 (这里只是自己的一些总结) ...图灵机号称可以模拟实际计算机的所有计算行为,计算能力还超过现有的计算机。但是还是有图灵机无法做到的事情,就好像计算机并不能...
  • 《计算的本质》读书笔记

    千次阅读 2016-12-02 11:38:04
    心得:有限自动机->下推自动机(有限计算机)->确定型图灵机(临界点)->通用图灵机(全能计算机),软硬件可以相互模拟替代,并且没有通用机器不能实现的算法,而通用机器上的程序只不过是对一台确定型机器的模拟
  • 第十二周总结

    2019-11-24 19:03:10
    图灵机的特点:图灵机在理论上能够模拟现代数字计算机的一切运算,可以视为现代数字计算机的数学模型,是一种抽象的计算模型。 1.5 计算机科学的定义 1.5.1 计算机科学的学科定义 计算机科学的基本思路涵盖从理论...
  • 人工智能史话(二)

    2021-06-07 20:38:30
    图灵的理论是,“如果有一条无限长的纸带,那么图灵机可以模拟任意机械过程。”这使得图灵机从理论上证明了“人的思考过程可以机械化”这一命题。其隐喻是“虽然我还不知道人是如何思考的,以及人的思考到底有多复杂...
  • 无论是从图灵机衍生而来的人口迁移,植物学遗传学,生物突变等的模拟。 简单的规则可以建立一个复杂的世界,像这样的计算机按照相同的规则进行重复计算。 就像可以简单模拟运输流的184号法令一样,我编写了一个简单...
  • 什么是软件?

    2019-05-07 16:21:00
    冯诺依曼结构,图灵机,以模拟人为目标  软件的历史,实际上可以说是用机器模拟人的历史。不管大家(包括在这个历史过程中的参与者)有没有意识到,我们都有意无意的在计算机上模仿人类的行为。从冯诺依曼结构开始...
  • 在可计算性理论里,如果一系列操作数据的规则(如指令集、编程语言、细胞自动机)可以用来模拟单带图灵机,那么它是图灵完备的。这个词源于引入图灵机概念的数学家艾伦·图灵。虽然图灵机会受到储存能力的物理限制,...
  • 当我们知道每台计算机可以由通用图灵机代替时,就会出现矛盾。 由于该机器实质上是在磁带上写入和读取符号,因此图灵的机器对磁带进行简单的“来回”读取和写入应该会产生与电子计算机模拟中产生的相同感觉! ...
  • EveryDay-操作系统

    2019-01-21 16:52:08
    最早的计算机图灵机 其实就是把人在纸上计算的这个过程模拟出来---纸带机,有纸带和控制器 把菜谱载进来,然后做菜,就做出了菜。 把程序载进来,然后执行,就出相应的结果 然后,冯诺依曼说,把程序存到内存里...
  • 语言模型的深入理解

    2021-03-23 19:52:21
    理性主义认为人类的智能行为可以使用符号系统来模拟,智能的基本单位是符号,认知过程就是在符号的表征下进行符号运算,因此思维就是符号运算(有图灵机那味了)。他们主张采用公理化、形式化的方法,严格按照一定的...
  • Android程序设计基础

    热门讨论 2013-08-03 16:28:04
    他是SAS高级计算机实验室的联合创始人和高级研究员,也是www.planetandroid.com网站的创办人和ZDNet的专栏作家。除本书外,他还出版了Google Web Toolkit:Taking the Pain out of Ajax和Eclipse IDE Pocket Guide...

空空如也

空空如也

1 2
收藏数 34
精华内容 13
关键字:

图灵机可以模拟计算机