图灵机
图灵机
图灵机是一种更加精密的通用计算机模型，能够模拟实际计算机的所有计算行为。
自然语言表达
图灵机可以描述为具有以下配件和功能的机器：
- 一根无线长的纸带作为存储
- 一个读写头，能够在纸带上左右移动并执行读取和写入操作
- 一个内部存储，用于记录图灵机的当前状态
- 一个程序表，用来表达机器计算的逻辑
- 两个特殊的预置状态，接受或停止，当图灵机进入这两个状态之一就会停止运行
形式化表达
图灵机是一个 7 元组 ，参数具体含义如下：
参数 含义 状态集，有限集，存储图灵机所有可能的内部状态 输入字符表，有限集，在机器启动之前确定 图灵机存储中的字符表，有限集， 转移函数，图灵机的核心 初始状态， 接受状态， 拒绝状态， 其他概念
格局：在图灵机的计算过程中，当前内部状态、当前存储中的所有内容，当前读写头的位置组合在一起，构成当前图灵机的格局(configuration)，常用符号 表示
判定器：图灵机处理输入时只有三种结果：接受、拒绝、循环计算；对于任意输入都不产生循环的图灵机我们称为判定器
语言：由一个有限字符表产生的符合某种特殊性质的字符串的集合；事实上这也的确是我们日常生活中所谓的“语言”的精确定义
注意
这里提到的”符合某种特殊性质”这个修饰语并不是可有可无的，它决定了这个语言是否是可数集，同时也意味着语言的补集的存在
图灵可判定：如果一个语言能够被某一个图灵机判定，表示对于这个语言内的字符串，图灵机能在有限时间内接受，对于不在这个语言内的字符串，图灵机能在有限时间内拒绝，总之不会进入无限循环，则这个语言是图灵可判定的(Turing decidable)
图灵可识别：图灵可判定性质的弱化，若某个语言是图灵可识别的，则表示对于这个语言内的字符串，图灵机能在有限时间内接受，对于不在这个语言内的字符串，图灵机可能会在有限时间内拒绝，也可能会进入无限循环
图灵机的变形
上面讨论的都是经典的图灵机，而图灵机还有很多其他的形式（例如增加纸带的个数等），但是他们识别语言的能力都是相同的；
像这种在形式上发生变化但是在功能上保持不变的性质称为稳健性(robustness)；而图灵机具有惊人的稳健性，似乎在某种程度上也表示了图灵机的通用计算能力
下面是两个图灵机的经典变形：
- 多带图灵机：能够同时处理多条纸带的图灵机
- 非确定型图灵机：在计算过程中，机器可以在多种可能性动作中选择一种继续进行，其计算图是树形结构
指向原始笔记的链接思考🤔
这两个图灵机变形从形式上来看比经典图灵机要更加强大，但它们在能力上都是一样的；如今花样繁多的 AI 算法从能力上来说会不会也是等价的？
算法
算法
算法有多种表达形式，但大体上可以归结为两类：非形式化的概念性的描述，形式化的精确的描述
其中，非形式化的概念性的描述通常通过自然语言来表达；而形式化的精确的描述则需要借助图灵机来表达，其常常被定义为运行在图灵机上的一组指令集
为什么算法的精确定义需要用到图灵机？
个人理解：精确从某种意义上来说就是恰到好处的简单，一个步骤不多，一个步骤不少
必须承认，算法的直观理解的确不需要使用图灵机的概念，就像我们小学就会的竖式乘法，我们会在纸上按照特定的步骤写下我们的计算过程然后得出答案。尽管看上去很简单直观，但实际上还是太复杂了：手握笔在纸上腾挪的这个事情想要真正描述清楚并不是一件容易的事情
小测试
有兴趣的读者可以尝试：能否在 50 字以内把”如何列竖式来计算两个三位数的乘积”清楚地描述出来
想要获得算法的精确定义就需要大刀阔斧地化简，比如把计算过程的执行者换成电路。
我们可以很容易(可能也不太容易😢)设计出一个乘法电路，然后指着一堆密密麻麻的电线告诉别人这就是乘法算法。这目前看来完全没有任何问题，直到另外一个人也拿来了一堆错综复杂的电线，然后告诉你这是除法算法。
你们会发现一个几乎必然的事实：你们两个的电路并不相互兼容！你的乘法电路在不改变接线的情况下是无法执行除法算法的。
也就是说，过于简单的电路并不能够完全替代人类来进行通用的计算。那么什么东西能够执行通用计算，但是又不存在除了通用计算之外的多余的功能呢？
图灵机。这就是为什么算法的精确定义需要图灵机，因为图灵机是最简单的能够执行所有算法而不需要改变自身结构的东西。
指向原始笔记的链接
判定与识别
识别与判定
计算机的能力的确很强，但也有其局限性，有一些问题甚至不存在可解的算法，这是非常令人耳目一新的事情。
除了思想上的启发性，可计算性划定了计算这个抽象概念的边界，在一定程度上也划定了智能的边界。
可判定性
可判定性的定义由图灵可判定性给出，不再重复。不可判定性的存在不难理解，从可判定性的定义中就可以看出：只需要构造某个语言让图灵机陷入循环即可。
可识别性
可识别性的定义由图灵可识别性给出。比较令人惊讶的是，图灵不可识别性：存在一个语言，它不能被任何图灵机识别。
不可识别性本质上来说是两个无限集之间的规模比较：所有图灵机构成的集合是可数的，而所有语言的集合是不可数的。
更具体地，图灵不可识别的语言要从哪里寻找呢？这里列举一个不加证明的定理：
一个语言是可判定的，当且仅当这个语言本身和它的补都是可识别的。
根据这个定理，如果一个语言是可识别的，但又不可判定，那么这个语言本身或者它的补集有一个是不可识别的
思考
从上面的分析看来，可判定性与可识别性似乎只是问题本身的性质，但为什么说它们划定了计算的边界呢？
从工程的角度来看，我们需要解决的都是一些实际的问题，这些问题本身才是客观实在的，而计算实际上是一种求解问题的方法。实际上，我们总是先得到一个问题，然后再分析问题是否可识别或可判定，如果不可识别或不可判定，那么我们就可以直接改变问题本身或者求其近似解。
从逻辑分析的角度来说，计算的边界其实就是回答什么样的问题计算能够解决，什么样的问题计算不能够解决。图灵机是一个能力足够强大但又足够简单的具象的计算载体，所有的计算行为都有了明确的执行者，因此计算的含义得到了明确：就是在图灵机上发生的各种各样的操作。因此”可计算”这个集合中的元素是各种各样的问题，这些问题构成了计算的边界。
那么”可计算”这个集合里面到底包含哪些元素？这个问题其实和”自然数到底有哪些”等价。“可计算”集中包含了无限多的问题，这个概念本身是一个理论存在，实际上没法验证的东西。值得一提的是，尽管”可计算”集中包含了无限多的问题，但实际上也是整个问题集中的很少一部分，还有大量的问题是不可计算的。
注意
这里的”可计算”其实是非常严格的”可计算”，也就是绝对意义上的无限精度的”可计算”
精度决定一切
如果说某一个问题，图灵机并不能获得其无限精度的解，那么图灵机能不能获得一个有限精度的解？
援引《计算理论导引》中的一个不可计算问题：软件验证问题。问题本身描述如下：如果你有一个程序和一份它的说明书，你想设计一个程序来自动验证这个程序和它的说明书是否匹配。
直观上来说，这个问题应该是可解的，因为这个工作正是所有电子器件厂商正在做的，他们应当能够验证他们自己制造的东西与它的说明书匹配是否匹配。但这个问题是一个典型的不可计算问题。
是什么造成了这种直观理解与理论分析的差异？其实就是精度。
图灵可计算这个概念本身非常严苛！它隐含地要求问题的解具有无限的精度。但是从工程的角度我们并不需要无限的精度，只需要令人满意的精度。
例如对于软件验证问题，你是一个毫无道德感的老板，你并不关心你生产的东西与说明书是否匹配，只是为了从政策上蒙混过关，那么你完全可以设计一台只输出”接受”的图灵机。问题还是同一个问题，并且你成功的用图灵机解决了这个问题。虽然结果的精确度并不高，但已经足够让你满意了。
这个例子明显的说明了精度是计算的一个重要前提条件。而另一个问题也随之而来：如果我不考虑精度，图灵机可以解决所有问题；如果我需要无限的精度，图灵机智只能解决部分问题。那么如果我需要一个有限的精度，图灵机是否可以解决所有问题？在我不断提高精度要求，不断逼近无限精度的过程中那些不能被图灵机解决的问题是如何被踢出”可计算”这个集合的？
针对这些问题，我提出一个非常主观的猜想：在有限精度的情况下，图灵机可以在足够长的时间内解决所有的问题。
注意这里面出现了计算时间的概念，这是一个自然而然的引入，因为更高的精度总是意味着更长的求解时间，而当我们不断提高精度时，求解的时间也不断延长，直到问题从工程上变得”不可计算”。
在精度的作用下，被图灵机掩藏的复杂性显现了出来，问题 、计算主体 、精度 、计算时间 这四者之间具有复杂的关系。
应该有一个约束方程来描述他们之间的关系，暂时抽象地写作：
至于问题、计算主体、精度以及计算时间到底是如何形式化定义的，有待后续研究🧐
指向原始笔记的链接
可归约性
可归约性
定义
归约性(reduction)：将一个问题转化为另一个问题，且使得第二个问题的答案能够用于解决第一个问题
映射可归约性
可归约性的形式化定义有多种表达方式，其中一种是映射可归约性(mapping reducibility)。“用映射可归约性将问题 A 归约为问题 B”意思是：存在一个可计算函数，它将问题 A 的实例转化为 B 的实例。简记为：
笔记
这个可计算函数就叫做 到 的归约
图灵可归约性
这是映射可归约性的一个扩展，取消了可计算函数这么一个概念。而是直接在图灵机的计算过程中假设问题 A 可以通过某种神秘的方式判定，然后再来判断问题 B 是否可以判定了。
如果在问题 A 能够判定的条件下，问题 B 也能够判定；问题 A 不能判定的条件下，问题 B 也不能够判定，那么我们就说”问题 B 相对于问题 A 是可判定的”。同时，也称”问题 B 图灵可归约到问题 A”，记作
意义
归约性给出了一些看似不同的问题之间的内在一致性。
指向原始笔记的链接