计算机在现代社会发挥着越来越大的作用，上至天气预报，下至银行储蓄，日常生活的方方面面无不依赖于计算机。这不禁让人产生“计算机无所不能”的想法。那么，计算机能计算出所有问题的答案吗？其实，早在现代计算机出现之前的1936年，英国数学家图灵就已经知道了答案。不仅如此，他思考的是更广泛的问题：哪些问题能够用一台机器通过运算解决？
为了回答这个问题，图灵设计了一种用于计算的机器，正是后来以他名字命名的图灵机。
图灵于1946年设计的自动计算引擎（ACE）计算机，1952年在英国国家物理实验室投入使用
图灵机的结构非常简单，它由两部分组成：一个读写头，还有一条两边无限延长的纸带。纸带被划分为小格，每格中只能有0和1两种符号。读写头则可以处于有限种不同的状态，不过每个时刻只能访问纸带上的一个格子。整台图灵机的秘密在于所谓的“状态转移表”，它指示着读写头如何根据纸带上的内容运作。它由一堆非常简单的规则组成：如果在状态A的读写头对着符号x，那么对着当前格子写入符号y，将纸带或左移一格，或右移一格，或保持不动，然后转移到状态B等。不同的状态转移表可以完成不同的工作。可以说，状态转移表是图灵机的灵魂。
计算过程示意图（状态转移表）
在图灵机开始运算前，读写头被设定为某种初始状态，而纸带上的内容就是机器的输入。图灵机一旦开始运作，读写头就会根据状态转移表一步一步不停运作，直到读写头处于某种特殊的“停机”状态才会停止。这时，图灵机才算是完成了计算。这时，纸带上留下的内容，就是图灵机给出的答案。如果读写头一直没有进入停机状态的话，图灵机就会无止境地运转，永远给不出答案。实际上，平时笔算乘法的思维过程，跟一台图灵机非常相似：在每个时刻，我们只将注意力集中在一个地方，根据已经读到的信息，在纸上写下符号；而指示我们写什么怎么写的，则是早已背好的九九乘法表，以及简单的加法。如果将一个笔算乘法的人看成一台图灵机，纸带就是用于记录的纸张，读写头就是这个人和他手上的笔，读写头的状态就是大脑的精神状态，而状态转移表则是笔算乘法的规则，包括九九乘法表、列式的方法等。
图灵机模型
普林斯顿大学里的图灵档案
图灵机看似简单，但它能解决的问题可不少。只要用足够的纸带和时间，一台合适的图灵机就可以模拟我们日常使用的计算机。计算机能解决的问题，图灵机也能解决，只不过所用的时间可能很长，因为图灵机的效率不高。实际上，图灵和另一位逻辑学家丘奇提出的设想，即所有可以计算的问题都可以用图灵机计算，被后人称为图灵——丘奇论题。到目前为止，我们仍然没有找到这个论题的反例，这也足以说明图灵的高瞻远瞩。
尽管图灵机的计算能力如此强大，但也有无数它不能解决的问题，其中最有名的恐怕是停机问题：面对一台正要开始运算的图灵机，已知它的状态转移表和纸带上的内容，在有限步的运算里，判断这台图灵机会不会无止境地运转。这个问题看似简单，却很重要。很多数学猜想，比如哥德巴赫猜想和黎曼猜想，都能归结成某个给定的程序是否会停止的问题。如果停机问题是可以计算的，那么我们就可以通过有限步骤的计算来解决那些猜想。所以，可以说停机问题比这些猜想都要难，要完全解决它恐怕不太可能。
而正是图灵，用严谨的逻辑证明了：图灵机不能解决停机问题。也就是说，不存在这样的计算方法，可以在有限步运算中，判断任意给定的图灵机在任意给定的输入下是否会停止。至此，我们终于找到了一个计算机不能解决的问题。
虽然停机问题看似与实际生活关系不大，但通过它，我们可以证明很多与日常生活息息相关的问题是计算机不能完美解决的。比如说，判断某个程序是否包含计算机病毒，用计算机程序是不能完全解决的。也就是说，不存在完美的杀毒软件，每个杀毒软件都只能查杀部分病毒，总会有漏网之鱼。所以，杀毒软件与病毒之间，永远是一场拉锯战：杀毒软件需要不停地更新，才能抵御层出不穷的病毒，而黑客又会编写出新的病毒来绕过已有的杀毒软件。
停机问题的意义远远不止于此。它开启了可计算理论这一计算机科学分支，令我们对计算机的能力有了更深刻的理解。而为了定义它引出的图灵机的概念，更是现代计算机科学的基础。在计算复杂度理论中，图灵机作为一种重要的模型，被用来比较不同计算问题的难度，从而为找到合适的解决问题的算法提供指引。在图灵机之后，又出现了众多的计算模型，但没有一个模型的重要性能望其项背。连逻辑学家哥德尔也认为图灵机是描述机械计算最合适的模型，因为它的机械化和高度的简洁。作为图灵的遗产，到了今天，图灵机仍然闪耀出智慧的光芒。（方弦）
【科学人】阿兰·图灵
图灵（1912—1954），英国数学家、密码学家、计算机科学家，英国皇家学会会员。他在年仅24岁时，就提出了“图灵机”以及“可计算性”的概念，解决了数学家希尔伯特提出的“可判定性问题”，为计算机的发展奠定了理论基础。在第二次世界大战中，他的惊人智慧在破译德国军队密码上做出了重要贡献，间接缩短了世界大战的进程。在第二次世界大战之后，他又投入到早期计算机的设计中。为了纪念他，1966年设立的计算机领域最高奖项被命名为图灵奖。
【微问题】如果一个提交给图灵机的问题不能被图灵机解决，人类的思维能解决吗？
【关键词】图灵机 可计算理论
- 笑为什么有益健康?
- 笑喷!萨摩学会写字,竟在死亡笔记上写下了仇家的名字。
- 笑尿!一位疑似被二哈附身的主人,两只狗狗见了吓得腿都软了。
- 笑死!一只猫有三块腹肌!然而我家猫表示我又十八块。
- 笑死了!汪麻麻给小奶汪们喂奶,结果有一只把嘴伸向了麻麻的菊花...
- 笑死了!网友家的猫咪染上偷窃的毛病,为寻失主他贴了这么一个招领启事。
- 笑脸和不笑的脸哪个更年轻?
- 符号+、-、×、÷、=是怎么来的
- 第一个为云分类的人是谁？
- 第一个为矿物制定颜色标准体系的人是谁？
- 第一个到达南极洲的人是谁？
- 第一个温室大棚是什么时候建造的？
- 第一个突破音障的人是谁？
- 第一个血库是何时何地建立的？
- 第一个被命名的恐龙化石是来自侏罗纪时期吗？
- 第一个进入太空的人是谁？
- 第一份植物专利是何时颁发的？
- 第一份气象图是谁制成的？
- 第一份英文版技术报告叫什么？
- 第一位太空游客是谁？
- 第一位航天员是怎么飞上太空的
- 第一位进入太空的女性是谁？
- 第一只成功克隆的动物是什么？
- 第一只成功克隆的哺乳动物是什么？
- 第一只进入绕地轨道的动物是什么？它是什么时候进入太空的呢？