Table of Contents:

图灵机

图灵机（Turing Machine）是图灵在1936年发表的 "On Computable Numbers, with an Application to the Entscheidungsproblem"（《论可计算数及其在判定性问题上的应用》）中提出的数学模型。在文章中图灵描述了它是什么，并且证明了，只要图灵机可以被实现，就可以用来解决任何可计算问题。

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

可计算问题

在计算机领域，我们研究的一切问题都是计算问题（Computational Problem）。它泛指一切与计算相关的问题。
A computational problem is a mathematical object representing a collection of questions that computers might be able to solve.

计算问题的一些举例：
* 给定一个正整数 n，判断它是否是质数
* 给定一个 01 序列，把它们按位取反
* 给定一个字符串，判断某个字符是否存在，及查找存在位置
* 给定一个逻辑蕴含的命题，求它的逆否命题

非计算问题的例子：
* 今晚吃什么
* 为什么太阳从东边升起

图灵完备

简单判定图灵完备的方法就是看该语言能否模拟出图灵机。
图灵完备意味着你的语言可以做到能够用图灵机能做到的所有事情，可以解决所有的可计算问题。

一个有图灵完备指令集的设备被定义为通用计算机。如果是图灵完备的，它（计算机设备）有能力执行条件跳转（if、while、goto语句）以及改变内存数据。 如果某个东西展现出了图灵完备，它就有能力表现出可以模拟原始计算机，而即使最简单的计算机也能模拟出最复杂的计算机。所有的通用编程语言和现代计算机的指令集都是图灵完备的（C++ template就是图灵完备的），都能解决内存有限的问题。图灵完备的机器都被定义有无限内存，但是机器指令集却通常定义为只工作在特定的、有限数量的RAM上。