数学缺口

kemin:这是我在研究计算理论时发现的数学缺口，都是阅读和思考的碎片，有待整理成学习经验记录。

这些天一直都研究计算理论。在搜集了一些资料并对其“扫描”般的通读一阵子后脑子虽然有点乱，但得到一个结论和一个问题。结论计算理论的三大内容--自动机、可计算性和复杂性。问题是为什么几乎所有资料一开始都涉及了看似无关的数学内容，这对于像我这样的数学基础不扎实的程序员来说可说是一只登山拦路虎。

• 为什么计算理论书一开始就讲集合、函数和关系、数学证明、语言等看似无关的东西？
• 为什么研究数学证明？因为解决问题是证明？因为证明要精确所以要数学？
• 有的书还讲述了逻辑，像定义、证明、定理和命题等概念？
• 为什么要给语言一个准确的定义？为什么扯到语言？与计算模型有什么关系？
• 是不是这些内容太基础或者是与实际计算问题抽象太远以至于我们一开始摸不着头脑呢？

定义是基础的基础。定义描述我们使用的对象和概念。任何数学定义必须是精确的。
就像鱼相忘乎江湖，人相忘乎道术一般，学习计算理论也忘乎计算与学习的联系。忘乎的原因在于悖论的出现。殊不知电脑是用电的脑？计算是对人脑的形式模拟。学习本身就是在计算。
人存在的终极目标是解决问题改造世界，而改造世界的前提是对世界的认知。前者是一个动态的过程，后者是一个相对静态的概念框架。

命题

• 为什么用语言来研究计算模型？

• from<<语言与机器>>

本书的主题内容是讲述“语言”是按照一定的规则生成字串的系统。字串是计算科学的基石。虽然我们一般都认为计算机是处理数字、文字和图片的设备，但更准确的说，计算机是在处理表达这些数字、文字和图片的符号串。

• from<<计算与自动机（领域入门专著monograph）Computation and automata. >>

自然语言和编程语言都可以看作句子的集合，也就是由一定的基本词汇作单元的有限字符串。“语言”这个词可以用作表达一个很宽泛的概念。既可包括我们一般所了解的自然语言，也可是各种不同的看似没有意义的语言。习惯上，我们关心的是语言的句法规范（标准）而忽略语言的语义方面问题。原则上可以为一种语句有限的语言给出它的句法规范。但是不可能为无限语句的语言给出句法规范。形式语言理论的主要任务就是研究无限语言的句法规范的有限性（study of finitary specfications of infinite languages）。
无论是基础的计算理论还是它的分支像密码学都不可分割牵涉到语言理论。一台计算装置的输入输出的集合可以看成语言。而从一个更精微的意思上看，计算模型本身也可以被某类别语言识别。例如，图灵机可以被0型语言识别，有限自动机可以被3型语言也就是正则语言识别。

• 逻辑规则给出数学语句的准确含义

研究逻辑是因为不是所有人都有很好的逻辑头脑，即使很好也不可能百分百精确。我们的目标就是要构造这样的一个精确的逻辑功能脑，电脑。

• 集合

离散世界相对于模拟世界更容易“精确”，更容易的用机械实现。集合是最一般的离散概念，特例有关系、序列、函数等。

• 证明