图林机器理论
理论介绍英国数学家A.M.图林在1936年提出的一个理想的机器的理论。这种理想的机器，后来被命名为图林机，它的结构非常简单，元件的功能非常弱。对这种机器可描述如下：有一条一端或两端无限伸长的纸带，上面划成一个一个的方格，方格内可印有字母或为空白。有一个元件叫做读头,它每次都注视一个方格,辨认其内容。读头可以不断地处在不同的状态中，也可以说接受不同的指令，然后根据读头注视方格的内容以及当时读头所处的状态或所接受的指令，决定机器当时的动作。
动作和状态动作分以下三种：读头左移(L)而注视左方一格；读头右移(R)而注视右方一格;读头印刷(P)一新字母或抹去原有字母，如果用 S0表示空白，则抹去原字母可以说是印刷S0；动作完了以后读头再转入一新状态，即接受一新指令。就图林机而言,方格内所能印的字母是有限个的固定的,设为 S0，S1，…，Sm（S0表示空白），机器可能处的状态或接受的指令也是固定的、有限的。设为q0，q1，…qn，并规定 q1为开始状态，机器开动时便处在状态q1中；又规定 q0为终止状态，而当机器处在状态q0时，便不再动作了。该机器的每个状态及其功能可刻划如下：
qiaLqj，qiaRqj，qiabqj。其意是,处在状态qi的读头,如果注视格内的字母为a,则读头左移或右移,或印字母b，然后转入状态qj。但q0则没有任何动作。由于引入终止状态 q0, 并要求除q0以外的任何状态qj对注视格内任何字母都应有所动作, 这样即使没有任何动作而转入qj，也能写成qiaaqj。
每个图林机器都可用字母表A={S0，S1，…，Sm}与状态动作表P={qiSaHbqj}（这里 Hb为L、R或一字母）来刻划，如果字母数为m+1，状态数为n+1，则状态动作表共(m+1)n行且q0不出现在最左端。虽然定有终止状态q0，但如果从 q1开始，永远转不到终止状态，则图林机必永远运转而不停止。凡对任何开始字均能停止的机器叫做必停机器，未必停止甚至可能永远运转的叫做一般的图林机。
在图林机上,未印字母的格叫做空格,印有字母的格叫做实格。如果规定纸带的两旁必须全是空格，设最左的实格到最右的实格之间所印的字母依次序为a1,a2,…，an，其间若有空格，则用字母S0表示之，这就使该纸带所表示的字为a1，a2，…an。如果读头恰好注视了其最左实格a1，则说读头标准注视了 a1a2…an。例如，有一图林机器Ц，它从标准注视字 P开始（状态为q1），根据机器的状态动作表而继续变动，直到出现终止状态q0为止，如果这时纸带上所表示的字变成了 Q，就表明机器Ц把P改造为Q,记为Ц(P)=Q；如果从标准注视P开始后，继续运转永远达不到终止状态，从而机器也永不结束，则表明Ц对P改造无结果，亦即Ц(P)无意义。
为了使用图林机计算数论函数，须用图林机器字母表上的字表示自然数。为此，最简单的方法是使用两个字母{S0，S1}，S0表示空白，S1相当于一竖,凡两旁为空格而中间有n+1个相邻实格的便表示数n，即用一个实格表示0,两个实格表示1等等。要表示三元数组(a,b,c)可使用一个空格、a+1个实格,一个空格、b+1个实格,一个空格、c+1实格和一个空格。设机器Ц从标准注视x（或标准注视 x1，x2，x3）开始，根据状态动作表而依次运转，直到Ц把 x变成ƒ（x）,（把x1，x2，x3 变成g(x1，x2，x3)）为止，就说机器Ц计算了函数ƒ(x)(函数g(x1，x2，x3))。但如果 ƒ(x)(g(x1，x2，x3)) 无定义，则要求Ц永不停止或虽停止而给一个表示无结果的信号，例如，S0，S1以外的任何信号。
使用领域表面看来,图林机器的功能是非常弱的。但是,只要提供足够的空间（纸带有足够长）以及足够的时间（步骤足够多），那末它的力量是非常强的，足以代替目前的任何计算机。实际上，任何递归半函数都可以用未必永停的图林机计算，任何递归全函数即任何一般递归函数（见递归论）都可以用永停的图林机计算。反之，凡能用一般图林机器计算的数论函数都是递归半函数，凡能用永停图林机器计算的数论函数都是递归全函数即一般递归函数，两者实质上是一样的。利用图林机器计算递归函数具有很大的方便性。数理逻辑学界一致承认可计算函数与递归函数是相同的，从而一函数是可计算的当且仅当它是可用图林机计算的。[1]