《计算的本质》拆书笔记思维导图

语法：规定程序看起来想什么样子(程序需要有一定的格式，编译器才能识别并编译)

语义：程序要表达的含义

操作语义(小步语义：从左至右一小步一小步进行；大步语义：递归就是一个典型)：把语言转换成真实的行为

指称语义：把语言成分映射为数学对象，定义在对象上的运算所表达出的语言的语义

总结：任何语言都有其含义，程序用某种语言编写当然也有其含义

确定性有限自动机：状态集合Q，字符表集合E，转换函数F，初始状态s，接收状态集合R；按规则输入字符串与接收状态是一对一关系

非确定性有限自动机：输入字符串与接收状态是一对多的关系(运用于正则表达式的通配符)

正则表达式：匹配字符串的规则

等价性：任何非确定性有限自动机都可以通过多状态模拟确定性有限自动机的单个状态，从而实现等价性

总结：最简单的机器实现了基本的字符串输入匹配，但是匹配多个’（’和’）’字符串时，有限状态自动机需要设置多个状态来实现

确定性下推自动机：自带栈的确定性有限自动机

非确定性下推自动机：自带栈的非确定性有限自动机

不等价：多重NPDA(栈组)和DPDA(单栈)不等价，因为无法将所有可能的栈组合成一个栈

总结：计算能力相比有限自动机有所提升，但是通过使用栈无法获得更多能力(例如模拟其他自动机)

确定型图灵机：能访问纸带的确定性有限自动机

非确定型图灵机：能访问纸带的非确定性有限自动机

最大能力：一条纸带可以存储多条纸带的内容，所以确定型图灵机和非确定型图灵机能力相同

通用机器：通过从纸带读取确定型图灵机规则、接受状态、起始配置(扮演图灵机规则手册解释器角色)，模拟其他确定性图灵机的机器

总结：确定型图灵机是有限计算器到全能计算器的临界点，任何程序都只是对规则手册的模拟。

模拟lambda演算：利用ruby语言简单的几个功能编写一个程序

实现lambda演算：定义规则手册，编写解释规则的解释器

总结：定义规则手册实际上就是程序的算法，实现这个算法需要简单的编程语言和对应的编译器

lambda演算：每一台图灵机都能由lambda演算程序模拟，而每一个lambda演算程序也能被一台图灵机模拟(软硬件可以相互模拟)

总结：因为任何硬件都可以通过模拟实现，所以通用性无处不在

基本事实：一台机器能执行任何算法；任何ruby程序能转换成等价的图灵机，反之亦然；代码即数据

可判定性：一个算法，任何可能的输入都能保证在有限时间内解决一个判定性问题

停机问题：对拥有一条特定纸带的特定图灵机判定他的执行是否能够停机

处理不可计算性：问一些不可判定的问题，如果找不到答案就放弃；把所问的几个小问题答案汇总起来，就能为一个更大的问题提供经验型的证据；问可判定的问题，在必要的时候要保守一些；通过把程序转换成更简单的东西来近似它，然后问关于近似的可判定问题

总结：不存在通用机器不能实现的算法，没有不可能的程序

抽象解释：把复杂的问题分解成更小、更简单，或者去掉未知的东西，但这样还能保留足够的细节，以便让它的解决方案与原始问题相关

静态语义：描述程序性质，无需执行就能研究(动态语义：定义代码运行时含义的方法)