0%

程序分析理论

序言

开帘顿觉春风暖,满纸淋漓白云声。

梳理程序分析重要又有趣的理论。

理发师悖论

村庄里有一位理发师,他说“我只给那些不给自己理发的人理发”。随着自己的头发越来越长,他陷入了困境。

如果他不给自己理发,那么他实际上是不给自己理发的人,他需要给自己理发。

如果他给自己理发,他就不是那些不给自己理发的人了,他不能为自己理发。

停机问题

证明:“计算机不是万能的。”

最准确&最易懂的版本

假设现在有两台机器 A & C:

A负责计算两个数的和,例如输入3、5,输出就是8;

C负责计算棋局下一步的最优解;

image-20210626171558276

A & C 都泛指正常的计算机程序:接收输入,输出结果。

对于只要能正常输出结果(不管结果对错)的程序,都可以称为该程序可以停机

对于程序陷入了死循环等问题,导致迟迟没有结果的输出的局面,那么该程序无法停机。

比如说A、C互换输入,那么就会导致出现停机。

这时候我们想有一台上帝的杰作H,H就是传说中的“上帝之眼”,给它读入任意一台机器的蓝图,以及任意一个问题(输入)后,它都能根据蓝图模拟出该机器的运作过程,从而判断出哪些问题(输入)会导致该机器出错(即无法停机),哪些问题则不会出错(即成功停机):

image-20210628093230413

那么这个H真的存在么?

接下来逻辑证明H是不存在的:

注意H的大前提是可以为任意程序蓝图+任意输入判断是否停机

假设现在有一个机器X:

image-20210628093607208

X由3部分组成:P、H、N

P负责将输入一分为二;

H是“上帝之眼”

N是反转器:

  • 如果H给出的结果是not stuck,那么N的结果就是stuck;
  • 如果H给出的结果是stuck,那么N的结果就是not stuck:)

现在,如果我们把X自身的蓝图给X,会发生什么?

此时H就会对X的蓝图判定,输入是X蓝图的情况下会发生什么?

如果H给出的是not stuck,那么X最终的输出结果就是stuck,相悖!

如果H给出的是stuck,那么X最终的结果就是not stuck,相悖!

所以X自身就是一个反例,因此逻辑层面就会证明,世界上根本不存在H

程序语言分类

两类:

  • DSL:特定领域语言。Domain Specific Language ,比如描述数据的JSON,标签型XML、HTML,查询语言SQL等等。
  • GPL:通用用途语言。General Specifc Language,主流编程语言,C/Java/JS/Go…,他们都是图灵完备的。

程序分析技术栈

canliture师傅