带你深入理解图灵机和图灵完备的概念定义以及有哪些作用和什么意义

我们来具体看下图灵机到底是什么？

一、图灵机的组成

网上有一张经典的图片来表达图灵机的构成，图如下：

这张图片什么意思？这么一个简单的机器/装置怎么会所有电子计算机的理论模型？

相信大家看到这张图后都有这样的疑问，下面笔者带来由浅入深去理解图灵机的组成。

图灵的基本思想是用机器来模拟人们用纸笔进行数学运算的过程，它运算过程看作下列两种简单的动作：

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

把注意力从纸的一个位置移动到另一个位置；

逻辑结构上图灵机有四个部分组成

一个无限长的存储带，带子有一个个连续的存储格子组成，每个格子可以存储一个数字或符号

一个读写头，读写头可以在存储带上左右移动，并可以读、修改存储格上的数字或符号

内部状态存储器，该存储器可以记录图灵机的当前状态，并且有一种特殊状态为停机状态

控制程序指令，指令可以根据当前状态以及当前读写头所指的格子上的符号来确定读写头下一步的动作（左移还是右移），并改变状态存储器的值，令机器进入一个新的状态或保持状态不变。

当然这些只是理想的图灵机，因为现实中不存在无限长的存储带，更加图灵的理论这样的一台装置就能模拟人类所能进行的任何计算过程。是不是很神奇？我相信你肯定不相信，不过图灵是经过严格的数学证明，下面我们来看看图灵机的计算过程。