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上。