计算理论 CH4
CH4: Turing Machine
4.1 The Definition of Turing Machine
前面的CFG和正则语言都有不可以判断的语言，我们结合FA以及pushdown automata来看，可以发现我对于读进来的语言中的字符串顺序一定是要从左到右，而图灵机本质上是对于这个读tape的过程进行了改进，使得对于tape不仅可以左右移动，而且可以write （前面相当于，FA我们只能按照一定的规则读入tape，PDA读tape，同时按照规则写stack；而我们的图灵机设法将两者结合，使得tape既可以读又可以写。）
对于图灵机的一个官方的定义：
这是图灵机的状态转移 这里需要注意的是，我们在图灵机的alphabet中，添加了四个特有的符号：空格，左终点的终止符，以及定义了向左和向右走（这里注意！向左和向右不在我的alphabet中） 以及定义了haulting state：也就是落在这样的状态下可以停下来（否则，图灵机可能一直向左向右乱走，可能陷入死循环停不下来）
transition（转移函数）：也就是在当前的状态和当前指向的字符下，会转移到另一个状态，并且要么左右移一格，要么改变当前的字符
一个例子：
这个的思路是：找到第一个a，换成x，一直往右走直到找到第一个b，换成y（表明找到了第一对ab）；然后一直向左走，去找第二个a，换成x，……以此类推。
4.1.2 configuration
图灵机的configuration分为三个部分：也就是当前指针有一个位置，这个时刻的快照包含了当前的状态、当前指针之前，从left end开始的字符串；以及当前指针之后延伸的字符串（去掉了后面可能有的无限个空格），如图所示
表示方法为，把当前的写在左边，或者写一个二元组，在当前磁带头指向的位置下划线标记。
对于图灵机computation的定义：
也就是说，两个快照之间可以一步转移，要么左右都一样只改了当前的（相当于修改），要么只是往左/右移动了一格
4.1.3 basic machine
也就是说，以Ma为例，相当于我无论读到了什么东西，都要把其修改为a，然后到haulting state。
四个简单的例子：
相当于是分别向左/右走，直到第一个空/非空的格子停下来
4.2 computing with turing machine
首先定义accept和reject： accept就是指我可以停在一个accept的state，reject指的是我可以停在一个reject的state 这个部分我们把图灵机判断的语言分成了几种； 1. recursive: 递归语言指的是可以在有限的时间内，被图灵机接受或者拒绝的语言 这个需要注意，意味着我的语言无论被你接受还是拒绝，都必须要停下来
（对于“递归”名字的一个可能的解释，比如说我的语言anbncn，根据前面的判定方法，相当于我们每一轮判断一个三元组(a,b,c)，一组一组判断相当于形成了递归。
容易想象，一共有可数无穷个递归语言
- Recursively Enumerable Languages：（递归可枚举语言）：简单地说，不属于这个语言的字符串不能停下来，属于这个语言的字符串一定可以停下来。
一个定理：
也就是相当于Re是一个更大的语言；构造方法是，让被递归语言否决的语言构造一个死循环，不让他停下来就可以了。
一个例子：
构造方法是，读到一个a就停下来；否则就一直走下去。
这里先剧透一下：上面的两种语言对应着所有的可计算语言
recursive language的性质：
递归语言的补（把yes和no互换一下）、并（把机器拼接起来）和交（可以先并行模拟，然后取其中两者交的部分）都是递归语言。同时，对于Kleene star其实也是封闭的
下面介绍的一个有用的部分是，将turing machine和函数结合起来：这里的核心思想是首先将整数使用二进制表示：这个很好理解，就是可以将我的每一个正整数对应成一个二进制的01串 接下来，其构成的逻辑如下：
这个就相当于输入我的字符串，经过一系列转换之后停机·，最终得到的就是我的函数输出结果
4.2.2 recursive functions
简单地说，这里的意思是，我有若干个输入，如果一个图灵机可以在有限的时间内
recursive：对于一个语言，给出任意一个字母表集合内的输入，图灵机都会停机到yes或者no的判断位置
递归可枚举：对于一个语言，给定一个输入，如果属于这个语言，那么停机；否则不会 
递归的一定是递归可枚举的；但是反之不一定成立；递归语言在补运算下封闭，但是递归可枚举语言不成立。
对于非确定性图灵机的判定问题： 首先明确，非确定性图灵机计算的不是一条路径，而是一一棵可能的计算树；对于上面的递归语言（必须停机，y属于语言，n不属于语言）和递归可枚举语言（停机接受，不停机不接受），这里非确定性有如下的扩展定义： 1. 递归可枚举语言：在这些计算路径中，只要有一条停机，那么接受；否则（全不停机）不接受 2. 递归语言：需要满足接下来的一系列条件才能接受： （1）需要所有路径都有限长（也就是说，存在一个足够大的N，使得没有一个路径在经过N步后还没有停机） （2） 存在至少一条计算路径，使得机器最终进入接受状态
如果是要能计算函数的话，那么需要非确定图灵机所有路径最后停下来的值是相等的 
更方便理解以上的三点
非确定性图灵机和确定性图灵机是等价的：这里的trick就是：对于非确定性图灵机，由于总的状态数和字母表数都是一个确定的值，这样一来每一步可能得到的（状态，操作）二元组数量也是有限的，我们希望确定性图灵机可以模拟一个广度有限的搜索，也就是按照非确定性向外第一层、第二层、第三层这样的模拟向外搜索 理解一下这个三带模型
第一个tape只用来记录一开始的输入，第三个
