英文
Turing machine
简介
一种理想计算机.它是由英国数学家图灵(Turing，A.M.)于1936年发明的.图灵对某个机械的演算过程进行分析后发现，计算员所实施的操作可以分解成下列的基本动作：认出某个符号，抹去某个符号，写出某个符号，转移观察点并更改记忆内容.由此，他设计了一种理想装置M(即图灵机)，它由一个双向无穷长的纸带和一个读头组成.纸带被分划成无穷多个两两相符的单元，每个单元中可以是空白的(记为B)，也可写上取自某个确定的字母表A中的一个字母.通常约定B亦在A中，并称A为M的字母表.读头在任何时刻都对准(或称注视)纸带上的一个单元.也可以在纸带上向左(记为L)或向右(记为R)移动一个单元.M还有一个内部状态集合Q={q0，q1，…，qn}，并且读头总是处在某个内部状态qi(qi∈Q)之下.图灵机M的运行由一个给定的有穷指令集合P所确定，P称为M的程序，其中的指令形如qisjqRslX，其中qi，qR∈Q，sj，sl∈A，X∈{R，L}.其含义为：当机器M的内部状态为qi，读头注视单元内的符号为sj时，M取新的内部状态qR，再把sj用sl替代，并且读头左移(当X=L时)或右移(当X=R时)一个单元.这样一来，只要在纸带上给定一个A上的串σ作为输入，再约定M在开始时取内部状态q0(称为初始状态)，而读头注视纸带上最左的非空单元，那么图灵机M便可依P中指令运行，直到在某一时刻机器取内部状态qn(称之为终止状态)为止，此时M便停机，纸带上的内容便是输出.若M一直取不到终止状态，则M将永远运行下去，此时M在输入σ后为发散的.
在上面描述中，M从开始运行到停机为止的整个过程称为计算过程，其中每用一次指令都称为计算的一步，整个计算过程的步数又称计算的长度.由上可知，在一定的约定之下，图灵机M被它的程序P所惟一确定.因此，给出M，实际上只要给出P即可，当然还要求P满足相容性条件：若P中两指令的第一、二分量相同，则它们必为同一条指令.
上述图灵机的运行是被输入惟一确定的，称为简单图灵机.此外还有其他形式的图灵机(参见“带外部信息源的图灵机”).另外，在保持计算能力不变的条件下，图灵机也还有许多不同的表述形式，例如具多纸带、多读头等.用哥德尔编码技巧，全体图灵机可以能行地排成一列：M0，M1，…，Me.其中e可称为Me的哥德尔码或下标.