图灵机(turing machine)

学过计算机的人总归会多或少得听说过图灵机这种东西，但是图灵机究竟是什么呢？图灵机其实也是自动机的一种，并且图灵机会在状态转换过程中操作一个无限的tape

tape的样子如下图所示，tape里面包含字符，其中后面那个两竖一横的符号是blank的意思，它是一个特殊的字符，用来填满无限的tape
在这里插入图片描述
tape head指向当前tape上的字符

tape上的操作

可以对tape head指向的字符进行读/扫描操作
可以对tape head指向的字符进行写/更新操作
将tape head左移一格
将tape head右移一格

操作规则：
1、
每一步操作都要执行一下操作

读取当前的字符
更新当前格子中的字符
左移一格或者右移一格

如果当前tape指向最左边的格子，那么执行左移操作将不会发生移动

如果你不想更改当前格的字符，那么执行更新操作的时候只要让它更新为和当前字符一样即可

2、
操作行为类似于有限状态机

有初始状态

终止状态有两种：

accept state
reject state

计算结束后状态会变成下列三种中的一种：

终止并且接受(accept)
终止并且拒绝(reject)
循环(loop，就是说没有终止)

下面是图灵机的正式定义，Turing Machine可以表示为一个七元组 $S,Σ,Γ,δ,s_{0},b,F)$

S是一组状态的集合
$Σ$ 是输入字母表
$Γ$ 是tape的字母表
$δ$ 是转换函数
$s_{0}$ 是初始状态
$b$ 是空符号
$F$ 是终止状态的集合(包括accept或reject)

转换函数 $δ$ 定义为:
$S×Σ\rightarrow Γ×(R/L)×S$

这里的(R/L)就是执行左移或者右移操作，R就是向右(right)移动，L就是向左(left)移动

以下面这张图为例，在图上 $0\rightarrow 1,R$ 代表的含义是，在状态A时接收字符0，那么将会转变为状态B，并且在当前磁头位置写下1这个字符，然后磁头向右移动一格
在这里插入图片描述

例子

接下来我们通过构建一个图灵机，并且实际运算一下，看看图灵机究竟是如何进行计算的

我们要构建图灵机，用于计算n+1函数，下图的初始状态是q1，结束状态是qa

在这里插入图片描述
假设输入的数字为1011（二进制），初始时tape head指向第一个值

在这里插入图片描述

第一步读取一个1，自动机会通过 $1\rightarrow 1，R$ 这个转换，转换后仍然变成 $q_{1}$ ，在第一格写入1，并将tape head右移一格
在这里插入图片描述
接下来的步骤和上面一样分别读取0,1,1仍然转变为 $q_{1}$ ，并且写上和原来相同的数字

这时候的tape head指向了空字符，按照状态机的转换 $q_{1}$ 只能转变为 $q_{2}$ ，要注意的是，tape head会往左移动一格

我们看看 $q_{2}$ 这边的转换，碰到1就写入0，并且向左移动tape head，因为按照二进制加法的逻辑，最后一位如果是1，那么+1后变成0，并且会进一位，如果最后一位是0，那么就直接变成1就行了，故此有了图上 $q_{2}$ 的转换