Python数据结构与算法01：概述：问题求解与图灵机模型

注：本文所有代码均经过Python 3.7实际运行检验，保证其严谨性。

本文阅读时间约为3分钟。

问题求解的计算之道

在漫长的历史当中，数学成了一个最终的终极工具。

为什么？

第一，数学具有清晰明确的符号表述体系。

第二，严密确定的推理系统。

希尔伯特提出一个基于有穷观点的能行方法。

所谓基于有穷观点的能行方法：

• 由有限数量的明确有限指令构成；
• 指令执行在有限步骤后终止。
• 指令每次执行都总能得到唯一结果。
• 原则上可以由人单独采用纸笔完成，而不依靠其它辅助。
• 每条指令都可以机械地被精确执行，而不需要智慧和灵感。

最后，“能行可计算”成为了计算机的基础。

图灵机计算模型

图灵机Turing Machine

1936年，Alan Turing提出的一种抽象计算模型。基本思想是用机器模拟人们用纸笔进行数学运算的过程，但比数值计算更为简单。

图灵机的基本概念

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

把注意力从纸的一个位置转向另一个位置。

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

• 此人当前所关注的纸上某个位置的符号；
• 此人当前思维的状态。

图灵机的组成部分

• 一条无限长的分隔纸带，每格可以记录1个符号。
• 一个读写头，可在纸带上左右移动，能读出和擦写格子的字符。
• 一个状态寄存器，记录有限状态中的1个状态。
• 一系列有限的控制规则：某个状态，读入某个字符时：要改写成什么字符；要如何移动读写头；要改变为什么状态。

图灵机的组成部分如下图所示：

图灵机的组成部分

图灵机的每条规则由5个部分构成：

1. 当前状态。
2. 当前读入的字符。
3. 要修改成什么字符。
4. 如何移动读写头，比如左移还是右移，还是不动？
5. 移动读写头之后，改变成了什么状态。

图灵机的某条规则 < s0, a, B, s1, R >的解释是，在s0（初始状态）下，读写头读到了a，把a变成了B，于是状态变成了s1，然后读写头向右移（s1就是读写头向右移的这种状态）。

To be continued.