图灵机模型

图灵机模型

-

2023年3月1日发(作者：孔雀东南飞教案)

数据结构与算法——1.问题求解的计算之道和图灵机计算模型

⽂章⽬录

⼀、问题求解的计算之道

⼈们在⽣活、⽣产、学习、创造的过程中总会遇到各种各样的问题。为了解决这些问题，⼈们使⽤占⼘、求神、经验、数学、实验、模型、

哲学等各种各样的⽅法和⼯具。⽽其中数学才是解决问题最强有⼒的⼯具，尽管数学本⾝也存在着很多问题（有些问题⽆法⽤数学语⾔明确

表述、或者有些可明确表述的问题仍⽆法解决）。

1.基于有穷观点的能⾏⽅法

为了解决数学本⾝的可检验性问题，数学家希尔伯特提出“能否找到⼀种基于有穷观点的能⾏⽅法，来判定任何⼀个数学命题的真假”。

这种⽅法的特征如下：

由有限数量的明确有限指令构成；

指令在执⾏有限步骤后终⽌；

指令每次执⾏都总能得到唯⼀结果；

原则上可以由⼈单独采⽤纸笔完成，⽽不需要依靠其他辅助；

每条指令可以机械地被精确执⾏，⽽不需要智慧和灵感。

2.关于“计算”的⼏种数学模型

哥德尔和克莱尼的递归函数模型；

丘奇的Lambda演算模型；

波斯特的Post机模型；

图灵的图灵机模型。

以上的⼏种“基于有穷观点的能⾏⽅法”的计算模型，全部都是等价的。也就是说，在⼀个模型中能解决的问题，在其他模型中也是可以解

决的。

希尔伯特的计划最终被证明⽆法实现。但**“能⾏可计算”概念成为计算机理论的基础**，⽐如：图灵机成为了现代计算机的理论基础。

⼆、图灵机计算模型

1.图灵机（TuringMachine）基本概念

图灵机是⼀种理论上的数学模型或者说抽象的机器，并不是某台具体的机器。基本思想是⽤机器模拟⼈们⽤纸笔进⾏数学运算的过程，但⽐

数值计算更简单：

在纸上写上或擦除某个符号；

把注意⼒从纸上的⼀个位置转向另⼀个位置；

在每个阶段，要决定的下⼀步动作依赖于：

（1）此⼈当前所关注的纸上某个位置的符号；

（2）此⼈当前思维的状态。

2.图灵机的基本定义

图灵机由以下部分构成：

⼀条⽆限长的分格纸带，每格可以记录⼀个符号；

⼀个读写头，可以在纸上左右移动，能读写格⼦上的字符；

⼀个状态寄存器，记录有限状态中的1个状态；

⼀系列有限的控制规则（如何移动读写头，什么状态下写⼊什么字符等）。

图⽚来源于⽹络，侵删。

图灵机模拟器软件：VisualTuring