今天有朋友说，奥呦，学数学的一般都不在意以后能赚多少钱，你看看那XXX ，XX ，XXX都是很清贫的过一生的。

我告诉他，别忙下定论，如果数学人解决这七个问题中的任何一个，是可以拿到百万美元大奖的。但这些问题并不会是那么好解决的，因为涉及到图灵机。

他立马发问：什么是图灵机？百万美元大奖是怎么和图灵机扯到一起的？

我用鼻孔“哼哼”两声，这说来就话长了。为了能给你这种专业的人解释清楚这个问题，我得给你科普如下五个问题。

首先，什么是图灵机？

图灵机是英国数学家Alan Turing于1936年提出的一种抽象计算模型，即将人们使用纸笔进行数学运算的过程进行抽象，由一个虚拟的机器替代人类进行数学运算。

Turing的基本思想是把人们纸笔运算的过程视为两种基本操作的复合：

a.在纸上写上（或者擦除）一个符号；

b.将读写头从一个位置移动至另一个位置（类似于写字时笔尖的移动）。

在任一阶段，人要经历的下一步行动取决于他所关注的位置上面的符号以及此人彼时思维的状态。

其次，图灵机的结构是什么样的？

a.图灵机有一条无限长的纸带，纸带被划分为若干个小格子。每个格子里填有一个符号，符号来自一个有限的字母表。纸带上的格子从左到右依此被编号为 0，1，2，... （任意非负整数）。

b.一个可移动的读写头。读写头可以读取或者改变当前小格的符号。

c.一套控制规则。其根据当前机器所处的状态以及当前读写头所指的格子上的符号来确定读写头下一步的动作，并改变状态寄存器的值，令机器进入一个新的状态。

d.一个状态寄存器。它用来保存图灵机当前所处的状态。图灵机的所有可能状态的数目是有限的，并且有一个特殊的状态，称为停机状态。

由于图灵机存在一个潜在的无限长纸条，所以它是一种理想化的装置。

第三，图灵机的工作原理是什么？

一台图灵机可以视为一个7元族{Q，Σ，Γ，δ，q0，qaccept，qreject}，Q ,∑ ,Γ都是有限集，且满足：

a.Q是状态集；

b.∑是输入字母表，不含特殊的空白符；

c.Γ是带字母表，且Q∈Γ, Σ∈Γ；

d.δ：Q×∑→Q×∑×{L，R}是某个转移函数，其中L和R代表读写头向左（向右）移动；

e.q0∈Q是起始状态；

f.qaccept是接受状态；

g.qreject是拒绝状态，且qreject≠qaccept。

图灵机M={Q，Σ，Γ，δ，q0，qaccept，qreject}以如下方式运行：

开始的时候将输入符号串从左到右依次填在纸带的格子上， 其他格子保持空白（即填以空白符）。M 的读写头指向第 0 号格子， M 处于状态 q0。机器开始运行后，按照转移函数 δ 所描述的规则进行计算。例如，若当前机器的状态为 q，读写头所指的格子中的符号为 x，设 δ（q，x）= （q'，x'，L），则机器进入新状态 q'，将读写头所指的格子中的符号改为 x'，然后将读写头向左移动一个格子。若在某一时刻，读写头所指的是第 0 号格子，但根据转移函数它下一步将继续向左移，这时它停在原地不动。换句话说，读写头始终不移出纸带的左边界。若在某个时刻 M 根据转移函数进入了状态 qaccept， 则它立刻停机并接受输入的字符串； 若在某个时刻 M 根据转移函数进入了状态 qreject， 则它立刻停机并拒绝输入的字符串。

由于δ是一个部分函数（即对于某些(q,x)δ无定义）。若图灵机运算时遇到无定义的情况时，将直接停机。

第四，什么是P复杂度和NP复杂度？

复杂度类P是在多项式表示的时间内，可以用确定性图灵机解决的所有问题。而复杂度类NP包括所有可以在多项式时间内验证正确解的决策问题，或者等效地，那些可以在非确定性图灵机上的多项式时间内找到的问题。

如果一个问题能找到一个算法，可以在多项式时间内解决它，那么问题就是P。

NP问题是在多项式时间内可以验证解的问题。NP问题的另一个定义是在多项式时间内可以猜测解的问题。

第五，拿奖的关键点来了：什么是P对NP问题？

显然，所有P问题都是NP问题。换句话说，如果你能在多项式时间内解决一个问题，你必然能够在多项式时间内验证一个问题的解。P对NP问题的关键在于，是否存在一个算法，使得在多项式时间内可以同时验证、解决某个问题。

若运用集合概念，我们可以把P问题全体组成的集合称为集合P，NP问题全体组成的集合称为集合NP，则P∈NP，则P对NP问题可以表述为：证明或者否定P=NP（即是否NP∈P）。

若P=NP成立，则其将把数学变成一门证明计算机可以为任何问题找到合理长度的学科。因为我们可以在多项式时间内验证证明是正确的。

目前P对NP问题仍然是数学和计算机领域悬而未决的问题之一。在2002年对于100名研究者的调查中，61人相信答案是否定的，9个相信答案是肯定的，22个不确定，而8个相信该问题可能所接受的公理独立，所以不可能证明或证否。所以P-NP问题也是Clay研究所的七个百万美元大奖问题之一。

我这么给你讲，您明白百万美元大奖和Turing的关系了吧？没有整明白？好吧好吧，P对NP问题很难，百万大奖的确不好拿，数学人解不出题，真的会很穷，哈哈哈。