图灵机原理及其不能解决的问题

图灵机

图灵将计算描述为状态变化的过程，以实现计算的自动化，从而产生了图灵机。

原理

将一台图灵机记为 M。 M具有一个有穷状态集S，任意时刻 M处于S中的某个状态（state）。S中有一个唯一的状态叫做开始状态，记为statestart∈S。S有一个子集叫做接受状态集，记为Saccept⊂S，Saccept中的状态称为接受状态；S还有一个子集叫做拒绝状态集，记为Sreject⊂S，Sreject中的状态称为拒绝状态。Saccept和Sreject不相交（Saccept ∩ Sreject=∅）。也就是说一个状态不能既是接受状态又是拒绝状态。

M配有一个有限的字符集合Σ，例如Σ={α, β, γ}。 令Σ∗为这样的集合：它的元素是所有由有限个Σ中的字符连接而成的字符串。对于举例的Σ来说，所有由有限个α,β或γ连接而成的字符串ω都属于Σ∗，例如ααβγ。字符串ω包含的字符个数是ω的长度。长度为 0 的字符串叫做空字符串（ Null String ），它也属于Σ∗。M以某个ω∈Σ∗作为输入。

M还配一个无限长的带（ Tape ）。带被分成一个个单元格（ Cell ）。每个单元格上可以写一个字符。M有一个读写头，总是位于带的某个单元格之上。读写头可以对当前单元格进行读和写，还可以沿着带左右移动，但一次只能移动一个单元格。 允许M在带上读写的全部字符构成了带字符集Γ。Γ包含Σ(Γ⊃Σ)。Γ还可以包含Σ中没有的字符。这些字符不能用来构造输入字符串ω，但可以被M在带上读和写。Γ必须至少包含一个Σ中没有的字符——空白字符（注意不是空字符串，而是一个表示空白的字符）。

在M运行的每一步，它根据当前状态和读写头下的字符，擦除当前单元格的旧字符并写下某个新字符，将读写头向左或右移动一个单元格，进入某个新状态（新状态也可以就是本来的状态）。决定M如何动作的规则就是M的转移函数 δ:S×Γ→S×Γ×{left,right}。例如δ(state1, ′3′)=(state5, ′7′, right)，意思是当M处于state1且读写头下的字符是 3 时，擦掉 3 写下 7 ，读写头向右移动一格，进入state5。一个 7 元组M=(S, statestart, Saccept, Sreject, Σ, Γ, δ)就定义了一台图灵机M。不同的 7 元组定义不同的图灵机。

要启动M，首先将输入字符串ω∈Σ∗写在带上（位置任意），其余单元格都是空白字符。令M的读写头对准ω的第一个字符，并让M处于statestart。这时M就开始一步一步地运行：读字符、覆写字符、移动读写头、进入新状态，然后再重复...... 直到M进入某个接受状态或某个拒绝状态，这时M停机。如果进入的是接受状态，则M接受ω；如果进入的是拒绝状态，则M拒绝ω。除了这两种情况，还有第三种情况：那就是M永远不停机——它既不进入接受状态，也不进入拒绝状态，而是一直运行下去。后两种情况合称M不接受ω。注意“接受、拒绝、不接受”三者的区别。所以对于某ω∈Σ∗，M要么接受它，要么不接受它。如果M不接受ω，有可能是M停机并拒绝ω，也有可能M不停机。

一个语言L（ Language ）是Σ∗的一个子集，即L⊆Σ∗。空集∅是一个语言——空语言。Σ∗本身也是一个语言，它包含字符集Σ上所有可能的字符串。能够被图灵机M接受的全体ω集合是一个语言，称为被M识别的语言，记作LM。对于每一个ω∈LM，如果将ω作为M的输入，M将进入接受状态而停机；对于每一个ω∉LM，将ω作为M的输入，M将进入拒绝状态而停机或者永不停机。

一台图灵机M可以被编码为一个字符串M~。M~按某种格式记录M的 7 元组。由于M的S只包含有穷个状态，其中哪个是开始状态、哪些属于接受状态、哪些属于拒绝状态都很容易标记。Σ和Γ都是有穷集合。δ的定义域和值域都是有穷离散集合。所以只要定义好格式，M就可以用一个字符串M~来编码。

例如：

图灵机能算 2 x 3 = 6 么？当把 10x11 （二进制的 2x3 ）作为输入字符串ω提供给一台图灵机，这台图灵机经过一系列动作后停机并在带子上留下 110 （二进制的 6 ），那么它就计算了 2 x 3 = 6 。

图灵-邱奇论题

该论题最基本的观点表明，所有计算或算法都可以由一台图灵机来执行。以任何常规编程语言编写的计算机程序都可以翻译成一台图灵机，反之任何一台图灵机也都可以翻译成大部分编程语言的程序，所以该论题和以

下说法等价：常规的编程语言可以足够有效的来表达任何算法。该论题被普遍假定为真，也被称为邱奇论题或邱奇猜想和图灵论题。