图灵机
A·M·图灵1936年提出的一种理论计算机。图灵对人的计算作了深入的分析研究，他认为人的计算工作可以归结为两种简单动作：(1)写下或擦掉一个符号；(2)将目光从纸上的一处转向另一处。根据这种看法，图灵提出了他的机器理论。
图灵机可以看作一种抽象的符号演算。也可以设想为一种物化的“机械装置”。后一种理解比较直观，为一般文献所采用。图灵机的这种“机械装置”主要是两项内容：
(1)一条可以向两端无限伸长的带子，称为工作带。工作带上划有大小相同的方格，每个方格可以容纳一个字母。
(2)一个可以沿工作带左右移动的读写头(每次移动一格)。读写头在不同时刻可能处于不同的内部状态(总共有有穷多个内部状态)。读写头在四元组的指挥下在工作带上进行操作，它的功能有三项：①认出它所对准的方格中的字母；②在所对的方格中打印一个字母(同时擦去该方格中原有的字母)；③左移一格或右移一格。
除了这个“机械部分”以外，图灵机还有一个指令组(或叫程序)，是由四元组(指令)所组成的有穷集，读写头在指令的指挥下工作。由于不同的图灵机之间的区别全在于指令组的不同，所以习惯上就将指令组与图灵机等同看待，给出一部图灵机就是给出指令组。
图灵机示意图
图灵机所使用的字母包含在字母表
｛S，S，S，…｝
之中(每部图灵机只用有穷多个字母)，S表示空格，常记作0或B；S也常记作1。为了计算函数，只要有两个字母就够了，不过，为简化过程，也常使用其他字母。
图灵机所使用的内部状态包含在以下序列
q，q，q，…
之中(每部图灵机只有有穷多个内部状态)，当读写头处于不同的内部状态时，面对同一个字母可以作出不同反应。
具有以下形状的符号序列称为四元组：
qSSq
qSRq
qSLq。
它们是指挥读写头动作的指令。
qSSq的意义是当读写头处于内部状态q读到字母S时，将S改为S，读写头内部状态变为q；
qSRq的意义是当读写头处于内部状态q读到字母S时，读写头右移一格，内部状态变为q；
qSLq的意义是当读写头处于内部状态q读到字母S时，读写头左移一格，内部状态变为q。一部图灵机(指令组、程序)是由若干四元组组成的有穷(可以为空)集合，并且其中没有两个四元组是以同样的qS开头的。这后一项要求是为了保证一次至多有一个四元组可用。
向图灵机Z输入自然数x，就是在Z的工作带上连续打印x+1个1(其余方格为空格，即印有字母0)，如下表所示：
简记作1。输入n元数组(x，…，x)是打印x+1个1，一个0，x+1个1，一个0，…，x+1个1，简记作
规定输入时读写头总是对准最左边的1，内部状态为q。
输入后，Z便在其四元组的指挥下进行运算。如果运算到某一步时不再有四元组可用(此时读写头内部状态为q，所扫描到的方格中印有S，而Z中没有以qS开头的四无元组)，运算便告结束，称为停机。停机时工作带上1的个数为输出。
从输入到输出的整个过程叫做Z的一个计算。
称由若干(至少一个)字母和恰好一个内部状态所组成的有穷序列(这个内部状态不是最右边一个元素)为瞬时描述。例如
S…SqSS…S
就是一个瞬时描述。它表示在该时刻该图灵机的内部状态为q，所扫描到的方格中印有S，该图灵机的工作带上有一段印有
S…SSS…S
其余方格中都是0。
输入n元组(x，…，x)时的瞬时描述为
，
称为初始的瞬时描述，停机时的瞬时描述为终止的瞬时描述。
图灵机Z的计算可以用瞬时描述的有穷序列
α，α，…，α
来表示，其中α是初始的瞬时描述，对每个i(1≤i＜n)，α是由α经Z的一个四元组的作用得到的，α是终止的瞬时描述。
应当注意，并不是每一部图灵机在输入每一个n元数组后都能停机的，例如图灵机
Z=｛q1Rq，q0Rq｝，
无论输入如何，它的读写头总是一味右移，永无休止。
给定图灵机Z，向Z输入的n元组与输出之间的关系是一个n元部分函数。记作
(x，…，x)或。
称为(由Z)图灵可计算函数：
设f为n元部分函数(无论用什么方法定义)，如果存在图灵机Z，使
f=，
则称f是图灵可计算函数。
常用的函数如零函数o(x)=0，后继函数x+1，投影函数(x，…，x)=x，加函数x+y，减函数x-y，乘函数xy，指数函数x，等等，都是图灵可计算函数，
定理：n元部分函数f(x，…，x)是图灵可计算的，当且仅当它是部分递归的。
由于图灵机的四元组只涉及可数无穷多个符号：S，S，…，q，q，…，R，L，而图灵机又只是四元组的有穷集。所以我们可以使用一个能行的方法将全体图灵机(无重复的)列出：
Z，Z，Z，…，Z，…。
文献中常将记作，称为第e号图灵机所计算的函数。
应当注意，对每个n≥1，图灵机Z唯一地计算一个n元部分函数；但对每个n元图灵可计算函数f(x，…，x)，却有无穷多部图灵机计算它(例如我们在Z中增加几条根本用不上的四元组得到Z′，Z与Z′所计算的函数完全一样)。因此函数序列
，，，…，，…
中包含了全部n元图灵可计算函数(部分递归函数)，而且每个图灵可计算函数在上述序列中出现无穷多次。
图灵机的指令也可以用五元组表示。例如五元组
qSSRq
的意义为：当读写头内部状态为q，读到S时，将S改为S，右移一格，内部状态变为q；
五元组
qSSLq
的意义为：当读写头内部状态为q，读到S时，将S改为S，读写头左移一格，内部状态变为q。
容易看出用五元组定义的图灵机理论与用四元组定义的图灵机理论是等价的。
图灵当初提出的图灵机就是用五元组陈述的，四元组的方法是E．L．波斯特1943年提出的。