计算理论学习笔记（三）
图灵机™
有穷自动机与图灵机区别：图灵机在带子上能写能读；读写头即能左移也能右移；带子无限长；进入拒绝和接受状态立即停机。
定义
格局
图灵可判定：有限步骤内，可知结果是yes或者no.
图灵可识别：有限步骤内，可知结果是yes.对于no的可能进入死循环.
图灵可补识别：有限步骤内，可知结果是no.对于yes的可能进入死循环.
识别语言的图灵机如图.
每次减半，直到1个0结束。中间出现奇数个0且不为1个，则进入拒绝态。
图灵可判定性
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-eXTOQWJa-1578220134348)(http://onwaier.com/wp-content/uploads/2020/01/83a5a5ea28d84514ff8205310442a94d.png)]
显然可判定，因为DFA对于每个输入的串要不进入接受态，要不进入拒绝态。采用的是标记法，类似于图中遍历。因为正则语言对于交，并，补运算都是封闭的，所以可以转成，而又能转成
[
CFG的相关的可判定性问题，很大程度上依赖于乔姆斯基范式。使用乔姆斯基范式能有限步内（2n-1步）判断能否识别某串。直接借用可判定的结论，来判断是否能派生串。KaTeX parse error: Expected 'EOF', got '}' at position 6: E_CFG}̲可判定同样采用标记法，不过是逆向标记。
证明思路类似于的证明.
可归约性
定义
证明不可判定，使用的是对角化方法。