形式化语言

2016-06-21 17:40:00

背景

之前并没有学习过语言形式化理论这门课，最多也就是了解编译原理，知道有个符号系统能够抽象词法，语法。通过研究这套符合系统的内在规律，给出了验证模型和相应的算法。恩，这就是我所了解的计算机程序原理。本科毕业之后，我觉的自己已经很好地掌握了计算机（组成，结构和程序）。但我不太懂：计算机干了什么，以致我们需要它？
首先，这不是一个好问题？为什么，因为这个问题有问题，有歧义，不同的人有不同的理解？
有人认为大数据计算，有人认为自动化，有人说是信息时代，降低生活成本，提高工作效率，还有人喊科技，创新等等。

其实我的意思是站在历史的角度，当时没有人知道有这么个东西的时候，最开始有这个想法的人，是如何定义它呢？
说起来这个人和计算机压根没关系，还不是他没见过计算机，而是他的贡献离我们太远了。韦达，这个十六世纪的法国数学家，第一次有意识地、系统地在数学中使用字母的学者。什么？这个不是常识吗，小学学的一元一次方程都是字母表示变量的好么。但是，在之前确实还真不是，而且我国在在辛亥革命之前，也不是啊，1906年，京师大学堂使用的教科书上，仍然用天、地、人、元表示未知数，用符号“⊥”和“|”分别表示加和减，分数则自上而下读。
不要说什么贡献小，事实上他的努力不仅推动了代数学的发展，而且对十七世纪的数学家和逻辑学家莱布尼茨启发很大。因此，使数学本身有一套完美的、通用的符号，成为莱布尼茨在数学研究中的努力追求。莱布尼茨本人创立的微积分符号体系。在他的符号体系中， dx 表示 x 的微分， ddx 和 dddx 分别表示 x 的二阶和三阶微分。尽管在创建微积分的过程中，牛顿也曾创立了另一种不同的符号体系。由于民族的偏见，英国的数学家曾在很长的时间内对莱布尼茨的符号体系进行抵制并坚持采用牛顿的符号。但终因莱布尼茨的符号体系更为便利，从而得到了普遍的应用并一直沿用至今。莱布尼茨的工作，导致了他在数学符号发展史上占据着重要的地位。直到今天，许多数学家都认为完美的符号系统促进了整个数学的发展。特别地，数学家克莱因对代数学的情况写道：代数学上的进步是引进了较好的符号体系，这对它本身和分析的发展比 16 世纪技术的进步远为重要。事实上，采取了这一步，才使代数有可能成为一门科学。” （《古今数学思想》，第一册，第 301 页）。
很多人其实不太懂，为什么大师会这么推崇符号系统呢？其实有点开始引进我们的目的了。当时的符号体系就是今天的数学语言，这个本质上就是数学语言相对比自然语言有什么优势？

无穷性就拿最简单的算术语言来说，它研究的对象是 0,1 ， 2 ，…， n ，…这些自然数的性质。之前的定理或当时的知识都有局限性，为什么，就是它验证的数据是有限的，自然语言喜欢来个整数，再说也研究不到那么多数啊！
统一性由于数学语言中使用了特定的记号，从而使数学语言成为一种半形式化的符号语言，这样以来，数学语言比任何一种自然语言更具有“统一性”。这就更明显了，以前一个村里两个人都还有分歧，更别说数学可以跨种族的，全世界的人都认识符号“∫”表示积分。
可操作性与自然语言相比，它与算法建立了联系。法国数学家违达提出：我们可以用字母（即符号）表示已知量和未知量，并对此进行纯形式的操作，也即我们可以摆脱问题的具体内容，而从一般角度总结出普遍的算法。比如求得任何一个一元一次方程的解需要5步：①去分母；②去括号；③移项；④合并同类项；⑤同除以未知数的系数。也就是抽象，把一个具体问题从它本身的场景中剥离，不管是土地啊还是黄金，都不管！你想想我们小学考试小明可是把所有水果啊、书本啊以及扫帚都算了一遍，可我们也就只会解一元一次方程（想想自己小时候不会写作业的时候的抱怨，可不就是笨嘛）。
另外数学语言与任何一种自然语言相比较，除了具有以上特点外，还具有无歧异性、简明性等特点。

恩，数学语言好，但不是最好的！啊，还有更好的呢！1879年，逻辑学家弗雷格就想了，数学好是好，但是有一点缺点，可操作性。不错这个可操作性不好，因为人太懒嘛！你说你虽然定下了一元一次方程的5步求解法，但是你每次都让我算一遍。我去，想起小明整天买这买那忙着给我们出题，也是辛苦极了。那能不能在增加一个可计算性呢，对不对！我一输入数字，你就被答案告诉我了。有算法（可操作性），有计算，恩！逻辑学家弗雷格越想越兴奋，发表了名著《概念文字——一种模仿算术语言构造的纯思维的形式语言》。

在这本书中，弗雷格借鉴了两种语言，一种是传统逻辑使用的语言，另一种是数学语言。从而成功地构造了一种逻辑的形式语言，即：一种表意的符号语言，并且用这种语言建立了一个一阶谓词演算系统，实现了莱布尼茨提出建立一种普遍语言的思想。

有同学看了上面的引用，借鉴两种语言，数学语言我懂，但传统逻辑使用的语言，我去什么鬼。其实这这样的，弗雷格想了想，人类是怎么计算的呢？一般人有了数学的可操作性之后，然后在人脑中进行计算，按照5步操作一步一步来。哎，这不就是人脑的逻辑嘛。说干就干：

他用“?-”表示判断符号，用“ ?﹁- ”表示否定符号，用“≡”表示内容统一符号，用“ F(A）”表示函数符号，等等。弗雷格使用这些符号，不仅表达了推理的形式和规则，而且还成功构造了第一个初步自足地逻辑演算系统。但是，他使用的符号不利于印刷。1910-1913年，罗素和怀特海发表了《数学原理》。在这部逻辑著作中，他们改进了弗雷格的表述方式，发展和完善了弗雷格的形式语言和形式推理系统。

但是有了逻辑，谁是大脑。没有大脑，怎么执行逻辑啊。所以就有了计算模型（为了可计算性）。大家一分析，人类所有的计算模型都包括如下四个要素：

输入集合或者输入变量（I）；
输出集合或者输出变量（O）；
处理或者变化（P）；
数据或者状态（D）。

即ComputingModel =（I，O，P，D）–注意其中用的是逗号（，），其中的输入输出是处理或者变化元素的输入输出。
当时正值两次事件大战，关于密码的破解和导弹管道计算迫在眉睫。图灵提出了一种计算模型：图灵机在已知输入输出情况下研究处理和数据的实现问题，即Turing’s machine = （I，O；P，D）–注意其中用的是分号（;），处理就是算法、程序Programming，数据是DataStructure。图灵机的工程化技术已经成熟，包括从汇编语言到UML语言在内的全系列软件工程和程序设计语言，核心是结构化程序设计语言。
后来我们也有一些不需要计算结果的需要，但是也需要计算。比如：一个机器，我按个按钮，它就唱歌，再按一些就停止唱歌。我了解它的状态，并且不需要计算结果。就提出了另一个计算模型： Petri网在已知变化状态条件下研究输入和输出的网络结构问题，即Petri nets =（P，D；I，O）–注意其中用的是分号（；）。图灵机是“从蛋（I，O）开始研究蛋（I，O）孵鸡（P，D）”问题，而Petri网是“从鸡（P，D）开始研究鸡（P，D）生蛋（I，O）”问题。两者精确对偶，统一起来就可以完全解决了“蛋（I，O）孵鸡（P，D）、鸡（P，D）生蛋（I，O）”的自然循环，因此被我统称为自然（或实）计算模型，目的是区别于我预计10年后才有可能研究成熟并公开的“虚计算模型”。
对偶定律告诉我们，对偶模型可以相互解决它俩各自所不能解决的问题。Petri网的实践（语用网）可以解决Turing机所不能解决的“软件模块复用（也就是计算协作）”问题；而 Turing机的实践（算法分析-也就是软件工程）解决了Petri网所不能解决的“节点爆炸”问题。这就是我把它俩统一起来研究的原因。