我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:2019跑狗图高清彩图 > 谕示机 >

图灵机模型

归档日期:07-13       文本归类:谕示机      文章编辑:爱尚语录

  语言与机器是我很早就想写的一个系列文章。大三时初次接触函数式编程就被这条不同寻常的“邪门歪道”所震惊。原来我们熟悉的过程是编程语言之外还存在这么多的“奇葩”。原来编程的思维不只有机器这一条路。仔细往下探究很快就会了解到丘奇的λ算子和图灵的图灵机,前者站在数学的抽象角度后者站在物理的机器视角。真正理解一件事物最好的方式莫过于去探寻它的历史,作为系列文章的第一篇,我们就一起回到20世纪初,寻找计算机产生的源头。

  希尔伯特(David Hilbert)在1900年巴黎数学家大会上提出著名的希尔伯特23问题。这23个问题对20世纪的数学界产生巨大影响,照亮整个20世纪的数学天空。此处我们只说明第2问题与第10问题,它们与我们后面要讲的故事有着莫大的联系。第2问题是有关公理系统的相容性:证明算术公理是一致的。第10问题是有关多项式丢番图方程解的问题:否存在一个算法,能够计算任意丢番图方程是否有整根。

  十九世纪下半叶,康托尔创立了著名的集合论。刚产生时,曾遭到许多人的猛烈攻击。后来数学家们发现,从自然数与康托尔集合论出发可建立起整个数学大厦。“一切数学成果可建立在集合论基础上”。 但是不久伯特兰·罗素(Bertrand Russell,1872—1970)提出了 一个悖论,可以用一个理发师问题进行通俗的描述:

  塞尔维亚有一位理发师:他只给所有不给自己理发的人理发,不给那些给自己理发的人理发。 问:他要不要给自己理发呢? 如果他给自己理发,他就属于那些给自己理发的人,因此他不能给自己理发。如果他不给自己理发,他就属于那些不给自己理发的人,因此他就应该给自己理发。(严格的罗素悖论: S由一切不是自身元素的集合所组成。 罗素问:S是否属于S呢? )

  许多数学家开始关心数学的基础问题。 数是什么? 无穷是什么? 公理应该如何? 空间应该如何?直观是否靠得住?当时的基础研究主要来源于四大支脉,它们彼此交叉:

  公理理论: 1899年希尔伯特的《几何基础》出版,是这个方向的里程碑。此后形成数学各领域中的公理化热潮,集合论也不例外。

  其中比较突出的当属公理化路线,危机产生后很多数学家和逻辑学家都在致力于给整个数学建立一个一致的公理基础,比如罗素和怀特海德写了 “数学原理” (Principia Mathematica) ; 比如约翰 ·冯 ·诺伊曼写了关于公理化集合论的博士论文 ; 再比如丘奇 (Alonzo Church)提出了λ算子(初衷是为了给逻辑学提供一个基础, 能代替罗素的类型理论和恩斯特 · 策梅洛 (Ernst Zermelo)的集合理论)。公理化路线的领军人物是希尔伯特:

  早期的几何学基础是欧几里得的《几何原本》所奠定的。但欧几里得体系有着许多缺陷。有些公理多余,许多概念诉诸直观。希尔伯特在一些人的影响下,提出来“在一切几何命题中,我们可以用桌子,椅子,啤酒杯来代替点,线,面”,这种思想后来导致他完成了几何学基础的彻底革新。1899希尔伯特发表的《几何基础》不仅彻底清除了欧几里得几何学体系中的缺陷,建立了新的几何学基础,而且树立了现代数学的公理化模式,发展了公理学,推动了整个数学基础的研究。 公理化的要点在于:

  公理系统中的每一公理是否符合人们的直观不予考虑,人们关心的只是公理系统中的公理是否彼此之间没有矛盾,也就是相容性。

  希尔伯特的公理系统是非常适合开展一个几何理论的。因此希尔伯特不仅为欧几里得几何学奠定了新的公理化基础,更重要的是建立一套模式来处理任何数学对象,并把他们建立在可靠的公理基础上。他还明确提出对公理系统的要求:

  无矛盾性,也称为协调性,一致性,相容性,也就是公理系统不能推出相互矛盾的结论。

  由于悖论的出现,数学的基础产生危机,以布劳威尔为代表的直觉主义主张抛弃经典数学中不可构造的结果,从而引起希尔伯特保卫经典数学“有成效的概念结构和推理方法”的努力;其结果就是提出“希尔伯特计划” 最终目的就是证明经典数学的无矛盾性,因而是可靠的。希尔伯特认为每一门数学理论都是由一些公理出发的演绎系统。数学理论的可靠性在于公理系统的无矛盾性。证明数学理论无矛盾性常用划归的方法,例如把非欧几何学的无矛盾性归结为算术的无矛盾性,算术的无矛盾性归结为集合论的无矛盾性等。如果最后能完成这些无矛盾性的证明,则整个数学也就有了可靠的基础。这就需要一个绝对的证明。

  一开始,“希尔伯特计划”取得部分成功,如证明命题演算,一阶谓词演算,只具有加法的算术的无矛盾性。但是哥德尔(Kurt Godel)1931年成功证明:任何一个数学系统,只要它是从有限的公理和基本概念中推导出来的,并且从中能推证出自然数系统,就可以在其中找到一个命题,对于它我们既没有办法证明,又没有办法推翻。 哥德尔不完全定理的证明结束了关于数学基础的争论,宣告了把数学彻底形式化的愿望是不可能实现的。

  “希尔伯特计划”原打算把所有古典数学,至少是其中大部分内容形式化。哥德尔第一不完备性定理证明这是不可能的。“希尔伯特计划”还试图通过有穷的证明来证明这样的形式系统的无矛盾。哥德尔第二不完备性定理表明,即使形式数论的所有方法都看成是有穷的,也不足以证明数论的无矛盾性(希尔伯特第2问题得到了答案)。

  哥德尔的论文发表之后,立即引起逻辑学家的莫大兴趣,它开始虽然使人感到惊异不解,不久即得到广泛承认,并产生了巨大的影响。它是20世纪数学的最重大成就之一,它是数理逻辑发展史上的里程碑。使得数理逻辑发展成“四论”,即递归论,证明论,公理集合论,模型论组成的数学分支。

  哥德尔不完备性定理说不存在一个完备的系统把数学彻底形式化。因为总有一些问题是既不可以证明“真”,也不可以证明“假”的。有些数学家看到这里会思考一个问题:哪些问题是可证明的?哪些问题是不可证明的? 边界在哪?怎么判定一个问题是否可解?这与希尔伯特第10问题(“是否存在一个算法能够计算任意丢番图方程是否有整根)也有着莫大的联系。要解决这个问题,就得先严格定义“可计算”这一概念。于是就引出了著名的”丘奇-图灵命题“。

  可计算的通俗说法:“设函数f的定义域是D,值域是R,如果存在一种算法,对D中的任意给定x,都能计算出f(x)的值,则称函数f是可计算的”,也就是在可以预先确定的时间和步骤之内能够具体进行的计算。在严格的可计算函数定义之前,数学家们经常使用“有效计算”这一非正式术语去描述那些可以通过笔和纸进行计算的函数。20世纪30年代许多数学家试图将可计算性理论形式化。其中三个典型代表是哥德尔,丘奇和图灵。他们的研究思路都是为计算建立一个数学模型,称为计算模型,然后证明凡是这个计算模型能够完成的任务都是可计算的任务。(这个模型就像一个评价器,判定哪些问题可解哪些不可解)。在可计算理论中,丘奇-图灵命题是关于可计算函数性质的猜想:自然数上的函数可以被人类按照特定的算法计算当且仅当它可以被图灵机计算。

  1933年,哥德尔(Kurt Gödel)和雅克·埃尔布朗(Jacques Herbrand) 一同建立了一类被称为一般递归函数(general recursive)的形式化定义。一般递归函数是最小的一类函数,它包含了所有的常函数,射影函数和后继函数并且对函数的组合运算与递归运算封闭。

  1936年,丘奇(Alonzo Church )所创造的形式化系统被哥德尔不完备性定理冲击之后,发现该形式化系统所包含的lambda算子(λ-calculus)具有良好的性质,并基于lambda算子定义了一种自然数的编码方式(丘奇数)。他证明自然数域上的函数是lambda可计算的(λ-computable )仅当对应的丘奇数上的函数可以被lambda算子表示出来。

  1936年,在得知丘奇的工作内容之前图灵(Alan Turing)创造了一种通过操作纸带上的符号进行计算的机器理论模型(图灵机)。把自然数编码成一堆符号序列,自然数上的函数是图灵可计算的(Turing computable )仅当存在图灵机可以在自然数被编码的符号序列上计算相应的函数。

  丘奇和图灵证明以上三种关于可计算函数的形式化定义是一致的:一个函数是λ-computable当且仅当它是Turingcomputable当且仅当它general recursive。

  冯·诺依曼根据图灵机提出了奠定现代计算机体系结构的冯·诺依曼体系结构,出现了机器语言,发展为汇编语言,最终形成了以C语言为代表的C类语言家族(C++,C#,Java等),它的计算原理是有限状态自动机,核心概念是“命令”。

  1965 年, 英国计算机科学家Peter Landin发现可以通过把复杂的程序语言转化成简单的λ算子,来理解程序语言的行为。这个洞见可以让我们把λ算子本身看成一种程序设计语言。 而众所周知的 John McCarthy的Lisp 语言,更是让λ算子广为传播。现在不论是各种实际的程序设计语言还是理论上的研究工作,λ算子都是一个绕不过去的基本工具了。λ算子之所以这么重要, 用 Benjamin C.Pierce的话说在于它具有某种“二象性”:它既可以被看作一种简单的程序设计语言,用于描述计算过程,也可以被看作一个数学对象, 用于推导证明一些命题。代表语言是Scheme、Haskell,计算原理是λ算子,核心概念是函数。

  代表语言Prolog/Mercury,计算原理是逻辑推理,核心概念是断言(Predicate)。

  本学期老师给我们上了一门研究生要上的课程:计算理论导引。起初还不是很理解的,后来觉得从0到1的创造出一个具有思维的及其,这的确是无比的伟大。Turing机:构造分为三部分:1。一条带,一个读写头和一个...博文来自:joyosue

  上一篇对图灵机得一些基本概念做了一介绍,这一节主要来模拟图灵机的运行。PAL(Palindrome)定义如下:对于任意的x∈{0,1}∗x\in\{0,1\}^*,如果xx是回文,则PAL等于1,否则...博文来自:YaphetsBin的专栏

  转自知乎:阿兰图灵和冯诺依曼,谁才是可称得起计算机之父呢?    答:都称得起。 ...博文来自:stpeace的专栏

  跟多答案:概率论与数理统计(第二版)吴传生编高等教育出版社第1章:随机事件的概率第2章:一维随机变量及其分布第3章:...博文来自:dinggang007的专栏

  图灵机的组成a.一条存储带:双向无限延长,上有一个个小方格,每个小方格,可存储一个数字或字母b.一个控制器:可以存储当前自身的状态,包含一个读写头,可以读,写,更改存储带上每一格的数字或者字母,可以根...博文来自:Just for our dream

  一、有限状态机引子让我们先来看几个简单的概念:状态       - 系统的基本数学特征。状态机     - 一个离散数学模型。给定一个输入集合,根据对输入的接受次序来决定一个输出集合。有限状态机 - ...博文来自:业精于勤,荒于嬉;行成于思,毁于随。

  图灵提出图灵机的模型并不是为了同时给出计算机的设计,它的意义我认为有如下几点:1、它证明了通用计算理论,肯定了计算机实现的可能性,同时它给出了计算机应有的主要架构;2、图灵机模型引入了读写与算法与程序...博文来自:weixin_36583895的博客

  上一篇介绍了天才图灵所做的时代背景,我们了解那个时代对于数学逻辑,可计算理论的发展。站在更大的时间和空间维度来看,我们看问题的角度会有更高的视角。这篇我们来具体看下图灵机到底是什么?从上一篇文章我们知...博文来自:weixin_34239169的博客

  图灵机,RandomAccessMachine,和算法的几个基本要素图灵机图灵机的一个简单例子RandomAccessMachine合理的创建标题,有助于目录的生成如何改变文本的样式插入链接与图片如何...博文来自:的博客

  在之前谈到了memorynetworks,其通过externalmemory扩展了神经网络的学习能力,但是其不是end-to-end,导致整个训练过程非常繁琐,甚至需要给训练集打上很复杂的标签,这里我...博文来自:kobepan1的博客

  图灵机模型与计算机(一)一、图灵机的构成1、一条无限长的纸带(tape)。纸带被划分为一个接一个的小格子,每个格子上包含一个来自有限字幕的符号,字母表中有一个特殊的符号,就是一个空格,它表示空白。纸带...博文来自:不忘初心,方得始终。

  前言图灵机和计算理论是人工智能乃至整个计算机科学的理论基础,邱奇-图灵论题告诉我们一切可计算过程都可以用图灵机模拟。图灵机图灵机,又称图灵计算、图灵计算机,是由数学家艾伦·麦席森·图灵(1912~19...博文来自:seaboat——a free boat on the sea.(公众号:远洋号)

  1.有一条无限长的纸带TAMP,划分为等大相邻的无数小方格,每个格子上可以容纳一个字符,字符来自一个有限集合,有一个符号表示空白。纸带从左侧开始编号为0.1.2.3.4...向右无限延伸。2.读写头H...博文来自:Mercuryf的博客

  有,而且还不少。他们被称为超计算(Hypercomputation)模型。超计算,是一个研究比图灵机计算能力更强的计算能力的计算机器的理论计算机科学分支。主要有以下部分模型: A.谕示机.(Oracl...博文来自:扩展の灰(Extended Ash/Cooevjnz)

  一、有限状态机引子让我们先来看几个简单的概念:状态       -  系统的基本数学特征。状态机      -  一个离散数学模型。给定一个输入集合,根据对输入的接受次序来决定一个输出集合。有限状态机...博文来自:WSN_IPv6的博客

  冯.诺依曼的模型并不是计算模型吧?它只是计算模型的一种具体实现而已,而且这个模型恰恰有效率地实现了图灵机的计算模型。简单对比一下,两者都依赖于状态的改变。我记得图灵机不就是用读写头去改变带子上的状态么...博文来自:明天的莜麦

  图灵机是图灵机理论中提出的理想模型,其可以实现任意复杂的计算。什么是图灵机英国数学家艾伦·图灵在1936年提出了「图灵机」的理论。「图灵机」设想有一条无限长的纸条,纸条上有一个个方格,每个方格可以存储...博文来自:This is bill的专属博客

  图灵机与C语言属于C语言入门教程,主要包括以下主要内容对图灵机的解释图灵机到C语言若干编程原则...博文来自:xuyuanjia02008的专栏

  图灵机,又称图灵计算、图灵计算机,是由数学家阿兰·麦席森·图灵(1912~1954)提出的一种抽象计算模型,即将人们使用纸笔进行数学运算的过程进行抽象,由一个虚拟的机器替代人们进行数学运算。所谓的图灵...博文来自:Zhangs Wikipedia

  阿兰·麦席森·图灵,被誉为“计算机科学之父”和“人工智能之父”。计算机逻辑的奠基者,提出了“图灵机”和“图灵测试”等重要概念。美国计算机协会(ACM)设立的以其名命名的“图灵奖”是计算机界最负盛名和最...博文来自:a little progress every day

  年前看了一本科普书籍–《人工智能简史》,作者尼克,早年任职哈佛和惠普,后投资创业。这本书描述了两大人工智能的发展方向,一派主张拟生物大脑(譬如人工神经网络),另一派则主张用逻辑和符号系统(譬如自动定理...博文来自:Camus

  一、图灵机的起源——可计算性理论在20世纪以前,人们普遍认为,所有的问题类都是有算法的,人们的计算研究就是找出算法来。1900年,当时著名的大数学家希尔伯特在世纪之交的数学家大会上给国际数学界提出了著...博文来自:haoxin963的专栏

  图灵机,java,源代码实现。计算机科学专业出身者一看就会知道是技术含量超高的好东东。玩编译必备!各位赶快下载吧!

  设计一个图灵机M,用于判定接收符合如下条件的字符串 C={aibjckdx}subject to i× j×k = x&i, j,k,x ≥1

  图灵机的java实现,通过txt文本文档载入图灵机,具体可见压缩文件内txt文本

  最近刚考完可计算理论,考前看习题总有一些题让设计一个图灵机来实现某个算法什么的(≖-≖)(虽然考试题里完全没有考到!然而我还是勤勤恳恳地想了很久)当时看图灵机定义看了无数遍,但依然不是很明白怎么设计啊...博文来自:机密母星联络处

  大计基作业中有这么一道题:答案是D项。那么如何实现这个图灵机的功能呢?首先想到需要创建一个不定长度的数组。实际上,如果让用户输入字符串的长度,再输入字符串,就没有什么意义了,所以才想到找个办法根据用户...博文来自:twentyonepilots的博客

  image.pngq111Rq1,其中前两个表示条件,后三个表示动作。(注意:先写入,然后再移动,不要搞反了)。H表示不动。多次不动将会到达停机状态。i1:q111Rq1i2:q1b1Rq2i3:q2...博文来自:weixin_34291004的博客

  TuringMachineHaltingProblem停机问题:指判断任意一个程序是否能在有限的时间之内结束运行的问题。图灵机停机问题是不可判定的,意思即是不存在一个图灵机能够判定任意图灵机对于任意输...博文来自:Zyj061的专栏

  1936年,阿兰图灵提出了一种可计算模型——图灵机。图灵机是从模拟人用纸笔计算的过程得到的灵感。图灵设想只存在于想象中的机器由一个控制器、一个读写头和一根无限长的工作带组成的。纸带起着存储的作用;读写...博文来自:zy010101博客

  上一节用单带图灵机模拟了PAL,其实可以用一种称为多带的图灵机来模拟,就像第一篇文章中介绍的那样,多带图灵机是具有多个读写头的图灵机。一个k带图灵机k带图灵机可以定义为一个四元组M=(K,Σ,δ,s)...博文来自:YaphetsBin的专栏

  来源,答案吧 概率论与数理统计(第四版)课后习题解析盛骤、谢式千编高等教育出版社第1章概率论的基本概念第2章随机变...博文来自:dinggang007的专栏

  帐号相关流程注册范围n企业n政府n媒体n其他组织换句话讲就是不让个人开发者注册。 :)填写企业信息不能使用和之前的公众号账户相同的邮箱,也就是说小程序是和微信公众号一个层级的。填写公司机构信息,对公账...博文来自:小雨同学的技术博客

  MATLAB编程题rn题目描述:从一个NxM的矩阵C中找出与1xM的矩阵P欧氏距离最小的某一行row,要求不能用循环!!!rn输入:矩阵C(NxM)、矩阵P(1xM)rn输出:rowrnrnrn解题思...博文来自:henryzhihua

  jquery/js实现一个网页同时调用多个倒计时(最新的)nn最近需要网页添加多个倒计时. 查阅网络,基本上都是千遍一律的不好用. 自己按需写了个.希望对大家有用. 有用请赞一个哦!nnnn//jsn...博文来自:Websites

  由于CLion的工程都是基于CMake来构建的,因此导入第三方库就需要在CMake文件中进行配置。这里把利用CMake导入第三方库的过程记录下来。...博文来自:大迷毛的LALALAND

  卷积神经网络是深度学习的基础,但是学习CNN却不是那么简单,虽然网络上关于CNN的相关代码很多,比较经典的是tiny_cnn(C++)、DeepLearnToolbox(Matlab)等等,但通过C语...博文来自:tostq的专栏

  扫二维码关注,获取更多技术分享nnn 本文承接之前发布的博客《 微信支付V3微信公众号支付PHP教程/thinkPHP5公众号支付》必须阅读上篇文章后才可以阅读这篇文章。由于最近一段时间工作比较忙,...博文来自:Marswill

  一、定义状态(State)模式又称为状态对象模式(Pattern of Objects for State),状态模式是对象的行为模式。状态模式允许一个对象在其内部状态改变时改变其行为,用于解决系统中...博文来自:小小本科生成长之路

  最近比较有空,大四出来实习几个月了,作为实习狗的我,被叫去研究Docker了,汗汗!nnDocker的三大核心概念:镜像、容器、仓库n镜像:类似虚拟机的镜像、用俗话说就是安装文件。n容器:类似一个轻量...博文来自:我走小路的博客

  本篇文章是根据我的上篇博客,给出的改进版,由于时间有限,仅做了一个简单的优化。相关文章:将excel导入数据库2018年4月1日,新增下载地址链接:点击打开源码下载地址十分抱歉,这个链接地址没有在这篇...博文来自:Lynn_Blog

  一、概述最近在springboot项目引入thymeleaf模板时,使用非严格标签时,运行会报错。默认thymeleaf模板对html5标签是严格检查的。二、在项目中加NekoHTML库在Maven中...博文来自:Luck_ZZ的博客

  本文介绍如何使用VS2015作为编译开发环境,调用OpenCV3.31和Qt5.9.1写图像处理的GUI。rn1.目录结构rn假设我们要创建一个名为VideoZoom的工程,那么首先按下图构建目录结构...博文来自:zhhp1001的博客

本文链接:http://williamzanker.com/yushiji/265.html