带你深入理解图灵机和图灵完备

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

　　一、比特币图灵机的组成

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

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

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

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

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

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

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

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

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

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

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

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

　　二、图灵机的运行机制

　　图灵机工作步骤

　　准备

　　存储带子上的格子初始话-设置内部状态存储器当前状态-读写头设置初始在存储带上所做的格子位置-准备好控制指令，即控制程序。

　　反复执行以下步骤，直到停机

　　读写头读出当前格子的数字或符号-根据当前状态和读到的字母或符号找到对应的控制指令-根据控制指令，执行以下三个动作1.读写头在格子上擦除或写入一个数字或符号2.变更状态到一个新状态

　　读写头向左或向右移动一格

　　估计你还是不明白，别急。看过《三体》的同学都知道三体人把地球人看做“虫子”，三体人的维度比地球三维世界高，就好像我们人类把看虫子一样。

　　下面，我们把虫子放到一个二维的世界中，以虫子为例，给大家来说明最简单的图灵机模型。