图灵机（Turing Machine）概念讲解与具体实例
图灵机Turing Machine历史起源：
1936年， Alan Turing提出的一种抽象计算模型基本思想是用机器模拟人们用纸笔进行数学运算的过程，但比数值计算更为简单 。
图灵机Turing Machine基本概念：
所谓的图灵机就是指一个抽象的机器，它有一条无限长的纸带，纸带分成了一个一个的小方格，每个方格有不同的颜色。有一个机器头在纸带上移来移去。机器头有一组内部状态，还有一些固定的程序。在每个时刻，机器头都要从当前纸带上读入一个方格信息，然后结合自己的内部状态查找程序表，根据程序输出信息到纸带方格上，并转换自己的内部状态，然后进行移动。
图灵机由以下几部分构成
一条无限长的分格纸带，每格可以记录1个符号，一个读写头，可在纸带上左右移动，能读出和擦写格子的字符，
一个状态寄存器，记录有限状态中的1个状态一系列有限的控制规则：
1. 某个状态，读入某个字符时， 2. 要改写成什么字符
3. 要如何移动读写头， 4. 要改变为什 么状态
在纸上写上或擦除某个符号；
把注意力从纸的一个位置转向另一个位置
在每个阶段， 要决定下一步动作依赖于：
- 此人当前所关注的纸上某个位置的符号
- 此人当前思维的状态。
实例-判定m个a和m个b模式串图灵机的规则 ：
例如：aabb a在前，b 在后，且 a和b的数目相等。具体操作过程是：开头擦掉一个a，挪到字符尾部擦掉一个b，擦除到最后一个是a,b测试停机“拒绝”状态，为B（空）则a和b的数目相等 停机“接受”状态。 具体操作过程如下，前面符号有点难以理解，可以看后面的文字解释：
<s0, a, B, s1, R>：初始碰到a消去， s1， 右移s0 是初始位置，消掉一个a后，转成s1右移<s1, b, b, s1, R>：遇到b， 继续右移， 找最后一个b<s1, B, B, s2, L>：右移到尾， 状态转为s2， 回(左)移B 表示字符前后空格-字符的终止符号<s2, b, B, s3, L>：如果有b， 消去， 进入左移状态s3<s3, b, b, s3, L>：左移遇到b， 继续左移<s3, a, a, s3, L>：左移遇到a， 继续左移<s3, B, B, s0, R>：左移到头回初始状态s0， 右移检查下个字符，重复上述过程
<s0, B, B, sY, N>： a,b都能一一消完， 则进入“接受(sY)”状态， 停机<s0, b, b, sN, R>： b多了， 或者b在a前， 进入“拒绝(sN)”状态， 停机s0碰到了b<s2, a, a, sN, R>： s2是末尾状态， 如果回(左)移碰到a， 表示a多了， 或者a在b后， 进入“拒绝”状态， 停机<s2, B, B, sN, R>： s2是末尾状态， 如果回(左)移没碰到b， 表示a多了， 进入“拒绝”状态， 停机
