图灵机中◁是什么符号(图灵密码图灵机标志)
图灵机中◁是什么符号(图灵密码图灵机标志)
你说的是图灵机吧！
所谓的图灵机就是指一个抽象的机器，它有一条无限长的纸带，纸带分成了一个一个的小方格，每个方格有不同的颜色。有一个机器头在纸带上移来移去。机器头有一组内部状态，还有一些固定的程序。在每个时刻，机器头都要从当前纸带上读入一个方格信息，然后结合自己的内部状态查找程序表，根据程序输出信息到纸带方格上，并转换自己的内部状态，然后进行移动。
一台图灵机是一个七元组 (Q,∑,Γ,δ,q0,qaccept,qreject)，其中 Q,∑,Γ 都是有限集合，且满足 1.Q 是状态集合； 2.∑ 是输入字母表，其中不包含特殊的空白符 □； 3.Γ 是带字母表，其中 □∈Γ且∑∈Γ ； 4. δ:Q×「→Q×Γ×{L,R}是转移函数，其中L,R 表示读写头是向左移还是向右移； 5.q0∈Q是起始状态； 6. qaccept是接受状态。 7.qreject是拒绝状态，且 。 qreject≠qaccept 图灵机 M = (Q,∑,Γ,δ,q0,qaccept,qreject) 将以如下方式运作： 开始的时候将输入符号串 从左到右依此填在纸带的第 号格子上， 其他格子保持空白(即填以空白符)。 M 的读写头指向第 0 号格子， M 处于状态 q0。 机器开始运行后，按照转移函数 δ 所描述的规则进行计算。 例如，若当前机器的状态为 q，读写头所指的格子中的符号为 x， 设 δ(q,x) = (q',x',L)， 则机器进入新状态 q'， 将读写头所指的格子中的符号改为 x'， 然后将读写头向左移动一个格子。 若在某一时刻，读写头所指的是第 0 号格子， 但根据转移函数它下一步将继续向左移，这时它停在原地不动。 换句话说，读写头始终不移出纸带的左边界。 若在某个时刻 M 根据转移函数进入了状态 qaccept， 则它立刻停机并接受输入的字符串； 若在某个时刻 M 根据转移函数进入了状态 qreject， 则它立刻停机并拒绝输入的字符串。 注意，转移函数 δ 是一个部分函数， 换句话说对于某些 q,x， δ(q,x) 可能没有定义， 如果在运行中遇到下一个操作没有定义的情况， 机器将立刻停机。
1936年，阿兰·图灵提出了一种抽象的计算模型 ── 图灵机 (Turing Machine)。图灵的基本思想是用机器来模拟人们用纸笔进行数学运算的过程，他把这样的过程看作下列两种简单的动作：
在纸上写上或擦除某个符号；
把注意力从纸的一个位置移动到另一个位置；
而在每个阶段，人要决定下一步的动作，依赖于 (a) 此人当前所关注的纸上某个位置的符号和(b) 此人当前思维的状态。为了模拟人的这种运算过程，图灵构造出一台假想的机器，该机器由以下几个部分组成：
一条无限长的纸带。纸带被划分为一个接一个的小格子，每个格子上包含一个来自有限字母表的符号，字母表中有一个特殊的符号 表示空白。纸带上的格子从左到右依此被编号为 0, 1, 2, ... ，纸带的右端可以无限伸展。
一个读写头。该读写头可以在纸带上左右移动，它能读出当前所指的格子上的符号，并能改变当前格子上的符号。
一个状态寄存器。它用来保存图灵机当前所处的状态。图灵机的所有可能状态的数目是有限的，并且有一个特殊的状态，称为停机状态。
一套控制规则。它根据当前机器所处的状态以及当前读写头所指的格子上的符号来确定读写头下一步的动作，并改变状态寄存器的值，令机器进入一个新的状态。
注意这个机器的每一部分都是有限的，但它有一个潜在的无限长的纸带，因此这种机器只是一个理想的设备。图灵认为这样的一台机器就能模拟人类所能进行的任何计算过程
图灵机停机问题(The Halting Problem)的不可判定性
图灵机停机问题: 能否给出一个判断任意一个图灵机是否停机的一般方法? 答案是NO.
这个问题实际上是问: 是否存在一台"万能的"图灵机 H, 把任意一台图灵机 M 输入给 H, 它都能判定 M 最终是否停机, 输出一个明确的 "yes" 或 "no" 的答案? 可以利用反证法来证明这样的 H 不可能存在. 假定存在一个能够判定任意一台图灵机是否停机的万能图灵机 H(M), 如果 M 最终停机, H 输出 "halt"; 如果 M 不停机, H 输出 "loop". 我们把 H 当作子程序, 构造如下程序 P:
function P(M) {
if (H(M)=="loop") return "halt";
else if (H(M)=="halt") while(true); // loop forever
}
因为 P 本身也是一台图灵机, 可以表示为一个字符串, 所以我们可以把 P 输入给它自己, 然后问 P(P) 是否停机. 按照程序 P 的流程, 如果 P 不停机无限循环, 那么它就停机, 输出"halt"; 如果 P 停机, 那么它就无限循环, 不停机; 这样无论如何我们都将得到一个矛盾, 所以假设前提不成立, 即不存在这样的 H. 或者说, 图灵机停机问题是不可判定的(undecidable)。
苹果公司的标志是设计人员和乔布斯思考之后的产物。之所以会缺了一块，也是因为bite与byte音似，以此来寓意苹果公司的创新精神
现在比较流行的说法就是苹果公司这样做是为了纪念计算机之父图灵，图灵设计的密码破译机在一定程度上影响了“二战”的格局。图灵是一位同性恋，这原本没有错，但不幸的是，当时的社会视同性恋为异端。图灵被当局强迫注射雌激素，导致身体遭受了极大的创伤。最后图灵不堪其辱，吃了一个含有氰化物的苹果，自杀身亡。
据说，苹果公司把这颗被咬了一口的苹果作为自己公司的Logo，是为了怀念这位伟大的“人工智能之父”。
这个故事虽然美好，但并不是苹果标志的真实起源。
苹果的标志最早的版本是一个牛顿在苹果树下读书的图案，寓意苹果公司要像牛顿一样积极思考，不断创新。但是这个图案太过复杂，很少有人能够真正记住苹果的标志，所以这个标志仅仅使用了几次之后就被乔布斯放弃了。
后来，乔布斯重新聘请了设计人员为公司设计标志，在设计之初，原本设计师提交的方案就是一个黑白的苹果剪影，但是乔布斯认为一个中规中矩的苹果太过死板，有可能会被认为是西红柿，不如被咬一口。况且，在英语中，咬了一口（taking a bite）和一个字节（a byte）发音相似，富有科技创新的意义。而且为了避免标志太过单调，设计者把黑白剪影换成了彩虹条，于是“被咬了一口的彩虹苹果”就此诞生。
阿兰·麦席森·图灵（Alan Mathison Turing，1912.6.23—1954.6.7），英国数学家、逻辑学家，被称为人工智能之父。 1931年图灵进入剑桥大学国王学院，毕业后到美国普林斯顿大学攻读博士学位，二战爆发后回到剑桥，后曾协助军方破解德国的著名密码系统Enigma，帮助盟军取得了二战的胜利。 阿兰·麦席森·图灵，1912年生于英国伦敦，1954年死于英国的曼彻斯特，他是计算机逻辑的奠基者，许多人工智能的重要方法也源自于这位伟大的科学家。他对计算机的重要贡献在于他提出的有限状态自动机也就是图灵机的概念，对于人工智能，它提出了重要的衡量标准“图灵测试”，如果有机器能够通过图灵测试，那他就是一个完全意义上的智能机，和人没有区别了。他杰出的贡献使他成为计算机界的第一人，现在人们为了纪念这位伟大的科学家将计算机界的最高奖定名为“图灵奖”。上中学时，他在科学方面的才能就已经显示出来，这种才能仅仅限于非文科的学科上，他的导师希望这位聪明的孩子也能够在历史和文学上有所成就，但是都没有太大的建树。少年图灵感兴趣的是数学等学科。在加拿大他开始了他的职业数学生涯，在大学期间这位学生似乎对前人现成的理论并不感兴趣，什么东西都要自己来一次。大学毕业后，他前往美国普林斯顿大学也正是在那里，他制造出了以后称之为图灵机的东西。图灵机被公认为现代计算机的原型，这台机器可以读入一系列的零和一，这些数字代表了解决某一问题所需要的步骤，按这个步骤走下去，就可以解决某一特定的问题。这种观念在当时是具有革命性意义的，因为即使在50年代的时候，大部分的计算机还只能解决某一特定问题，不是通用的，而图灵机从理论上却是通用机。在图灵看来，这台机器只用保留一些最简单的指令，一个复杂的工作只用把它分解为这几个最简单的操作就可以实现了，在当时他能够具有这样的思想确实是很了不起的。他相信有一个算法可以解决大部分问题，而困难的部分则是如何确定最简单的指令集，怎么样的指令集才是最少的，而且又能顶用，还有一个难点是如何将复杂问题分解为这些指令的问题。 1936年，图灵向伦敦权威的数学杂志投了一篇论文，题为“论数字计算在决断难题中的应用”。在这篇开创性的论文中，图灵给“可计算性”下了一个严格的数学定义，并提出著名的“图灵机”(Turing Machine)的设想。“图灵机”不是一种具体的机器，而是一种思想模型，可制造一种十分简单但运算能力极强的计算装置，用来计算所有能想象得到的可计算函数。“图灵机”与“冯·诺伊曼机”齐名，被永远载入计算机的发展史中。1950年10月，图灵又发表了另一篇题为“机器能思考吗”的论文，成为划时代之作。也正是这篇文章，为图灵赢得了“人工智能之父”的桂冠。
这几年由于区块链的大热，以太坊独特的solidity语言实现智能合约功能， 图灵完备 这个词走进大家的视线。
没有计算机专业知识的同学其实很难理解这个词的意思，其实计算机专业的同学都没有深入理解图灵机，图灵完备，图灵测试等概念包含的内涵。为了方便理解区块链技术，理解智能合约，笔者准备分几篇文章来带大家从浅入深，一步一步带你深入理解图灵机，相信通过这几篇文章能就能够理解什么是图灵完备。
艾伦·麦席森·图灵（Alan Mathison Turing，1912年6月23日－1954年6月7日），英国数学家、逻辑学家， 被称为计算机科学理论之父，人工智能之父。
1931年，图灵考入剑桥大学国王学院，由于成绩优异而获得数学奖学金。
1936年5月，年仅24岁的图灵发表一篇题为《论数字计算在决断难题中的应用》的论文，论文中提出一种计算装置，后被称为 “图灵机” ，图灵机不是具体的计算机，而是一种计算概念、计算理论。
1938年在普林斯顿获博士学位，其论文题目为“以序数为基础的逻辑系统”，在数理逻辑研究中产生了深远的影响；同年图灵回到英国，在剑桥大学国王学院任研究员。
第二次世界大战期间，1939年图灵到英国外交部通信处从事军事工作，主要是破译敌方密码的工作。由于破译工作的需要，他参与了世界上最早的电子计算机的研制工作。他的工作取得了极好的成就，破译了德国人Enigma密码，于1945年获政府的最高奖——大英帝国荣誉勋章。
1945年，图灵结束了在外交部的工作，他试图恢复战前在理论计算机科学方面的研究，具体研制出新的计算机来。
1950年他发表论文《计算机器与智能》（ Computing Machinery and Intelligence），为后来的人工智能科学提供了开创性的构思。提出著名的 图灵测试 。
1950年，1950年10月，图灵发表论文《机器能思考吗》。这一划时代的作品，使图灵赢得了“人工智能之父”的桂冠。此时，人工智能也进入了实践研制阶段。随着这几年AI技术的不断成熟，人们越来越认识到图灵思想的深刻性：它们至今仍然是人工智能的主要思想之一。
1954年6月7日，年仅41岁的图灵被发现死于家中的床上，床头还放着一个被咬了一口的苹果。这就是现在大名鼎鼎的苹果电脑公司logo的来源。
从图灵的生平中，我们知道，他出生在20世纪初，1912年。
在世界国家格局上，这个时候刚刚爆发第一次世界大战（1913~1921），紧接着1939年至1945年第二次世界大战，大家知道，这两次世界大战倒逼了很多科技的发展，二战期间恰好是图灵青年时代。
在科技文明发展上，由于逻辑的数学化，促使了数理逻辑学科的诞生和发展。但同时这个时期数学上发生了第三次数学危机，具体介绍在下方。图灵在剑桥读大学期间，修读了“数学基础”课程，授课人是纽曼，纽曼整个课程包含对哥德尔不完备性定理的证明和尚未解决的判定性问题。
这些科技事件的背后，其实是人们在认知上，对 可计算性理论 的研究，图灵正是这个问题终结者。
随便提一下，爱因斯坦1905年提出狭义相对论，1927年年仅15岁的图灵为了帮助母亲理解相对论，还写过论文的摘要。
在20世纪以前，人们普遍认为，所有的问题类都是有算法的，人们的计算研究就是找出算法来。1900年，当时著名的大数学家希尔伯特在世纪之交的数学家大会上给国际数学界提出了著名的23个数学问题。
其中第十问题是这样的：
“丢番图方程”指：有一个或者几个变量的整系数方程，它们的求解仅仅在整数范围内进行。
上面这个问题简单点解释是：随便给一个不确定的方程，是否通过有限的步骤运算，判断这个方程是否存在整数解。
这个问题在1970年，苏联一个数学家证明了其实很多数学问题，是没有答案，甚至没有答案的问题比有答案的问题还要多。
这里就提出来了有限的、机械的证明步骤的问题，其实就是算法。但在当时，人们还不知道“算法”是什么。实际上，当时数学领域中已经有很多问题都是跟“算法”密切相关的，因而，科学的 “算法” 定义呼之欲出。之后到了30年代的时候，终于有两个人分别提出了精确定义算法的方法，一个人是图灵，一个人是丘奇。而其中图灵提出来的图灵机模型直观形象。
图灵思考这个问题的方式和常人不一样，在写前面提到的论文《论可计算数及其在判定性问题上的应用》的时候，图灵在思考三个问题
图灵这样的天才考虑问题的认知是高屋建瓴的。
图灵首先考虑的是是否所有数学问题都用解，如果这个问题不解决，辛辛苦苦解题，最后发现无解，一切的努力都是浪费时间和精力。
对于存在答案的数学问题，只有部分是可以在有限步骤内完成，这样把计算机的边界确定下来了。
确定了边界之后，就要设计一种通用、有效、等价的机器，保证可以按照这个方法做事，最后得到答案。而图灵机就是图灵设计出来的这样的一个机器，严格来讲是一种数学模型、计算理论模型。
从图灵机提出到现在已经过去了80多年，今天所有的计算机，包括量子计算机都没有超出图灵机的理论范畴。
第三次数学危机产生于十九世纪末和二十世纪初，当时正是数学空前兴旺发达的时期。首先是逻辑的数学化，促使了数理逻辑这门学科诞生。
早在19世纪末的时候，康托尔为集合论做了奠基性的研究。人们发现，运用集合这个概念可以概括所有的数学，也就是说集合是一切数学的基础。然而就当这座大厦即将完工的时候，一件可怕的事情发生了，罗素提出来的罗素悖论粉碎了数学家的梦想。
关于罗素悖论的一个通俗化版本是：
为什么要第三次数学危机呢？
因为有个很重要的概念： 停机问题 ，停机问题是逻辑数学中可计算性理论中很重要的问题，也是第三次数学危机的解决方案。
停机问题 通俗地说，停机问题就是判断任意一个程序是否能在有限的时间之内结束运行的问题。该问题等价于如下的判定问题：是否存在一个程序P，对于任意输入的程序w，能够判断w会在有限时间内结束或者死循环。
有人猜测图灵机模型是图灵在思考 停机问题 而顺带设计出来的，是很有道理的。
图灵在剑桥大学国王学院期间，研究过一本叫做《量子力学的数学基础》的新书，这本书由年轻的匈牙利数学家约翰·冯·诺依曼所著。图灵意识到计算可以用确定性的机械运动来进行表示。其实我们现在的电子计算机虽然不是我们传统意义上的机械，但是CPU内部的电子运动等价于机械运动。
同时图灵也意识到人的思想、意识来自于量子力学中的测不准原理，这不光是微观世界，同时也是这个宇宙本身的规律。所以图灵意识到计算是确定性的，可判定的，而意识是不定的，不可计算的。
在AI人工智能有巨大发展的今天，很多人担心计算机是否会和人一样有意识，其实图灵在80多年前已经考虑过这个问题了。
前面提到，图灵在1950年写过一篇论文《计算机器与智能》，在这篇论文中，图灵测试一词被提出来：
这个测试有多难？目前我们所有的人工智能都没有完成这个测试。最近2018年3月份的谷歌I/O大会上演示的AI产品，据说“部分通过图灵测试”。这个部分到底有多少也未可知。
从人类科技发展的历史上来看，19世纪末到20世纪中期，是第二次工业革命和第三工业革命过渡的时期。第二次工业革命主要电和磁、内燃机的发明和使用，发展到这个时候科学家对世界的认知越来越多，越来越清晰，物理学和数学等自然科学发展迅速。这个时候的数学家发现很多现象可以用数学模型来表示，从物体的运动到星球的运动、从热能到动能的转换、从电到磁的转换等等。那问题来了是否所有的现象都可以用数学模型来表达呢？真是这个问题，让人们对数学很多根本性问题进行思考和研究。
中国有句古话说：乱世出英雄。在图灵的时代，在科学历史上出了很多的科学英雄，包括爱因斯坦、冯诺依曼、图灵、哥德尔等等，一方面是时代背景使然，一方面真是他们的天赋和努力让以信息化为代表的第三次工业革命的进程大大加快了。
从这些巨匠的思考问题，解决问题的方法和认知来看是超出常人的。从对 可计算性理论 的思考，给了我们很大的启示：
**更多有关区块链的技术与思维，可扫码加入我的小密圈。在这里，我陪着你，大家一起研究区块链技术，探讨区块链思维，预测区块链未来，一起做未来前10%的人
**
