一、图灵
如果提到计算机科学，那就不得不提一个人，图灵。如果用最简单的话语去描述图灵以及他的一生，其实只需要三个单词：战争英雄，同性恋以及计算机科学的缔造者。
图灵
还有一个以图灵命名的奖，由美国计算机协会（ACM）设立的计算机奖项，图灵奖。图灵奖是计算机领域的国际最高奖项，被誉为“计算机界的诺贝尔奖。要知道图灵可是英国人，真正发明计算机的是美国人，美国人居然不用冯·诺依曼来命名它，而是用图灵来命名这个奖项，可见图灵对现代计算机的影响。其提出的图灵机更是现代计算机的基础。
现在手头使用的智能手机、计算机都可以说是一种图灵机，即通过对输入进行计算得到输出的机器。图灵最早给出了这种机器形式化的定义和理论证明，并提出了图灵测试这一思想实验。
二、图灵机
在 20 世纪以前，人们普遍认为所有问题都是可计算的，也就是有算法可以解决的，即数学是万能的。
但是随着各种难以求解的数学问题的提出，渐渐有人提出了这么个问题，是不是所有的问题都可以计算？
这时候一位伟大的数学家出场了，那就是哥德尔，他提出了著名的哥德尔不完备定理，清晰有力的证明了，在自然数的公理体系中，数学是不完备的，并将无法完善。无论理论系统基于什么规模的公设，都有超出命题系统范围的真实陈述，有些数学真理，即使是真的，我们也无法证实。
同样是这个问题，图灵则设想了一个机器，通过描述机器如何计算来完成数学上的逻辑推演，从而证明可计算问题和计算的极限，这从一个全新的角度定义了可计算函数，也给出了比较具体的实现方式，他将计算归结为最简单、最基本、最确定的操作动作，非常直观的描述了计算的过程，这时候图灵机的概念也就浮出水面。
图灵机
图灵机就是一个黑盒机器，主要包括了 3 个部分：
- 输入集合，一个无线长的存储纸带。
纸带上有一个个小方格，小方格里可以写入一些 Symbols。这里用 0，1 和空 (NULL) 为例，也就是一个 3-symbol 图灵机。
- 输出集合，一个读写头；
读写头可以从小方格里读出 symbol。
清除一个小方格子里的内容，或者直接写入新的 symbol 覆盖原有的数据。
向左（右）移动。
- 控制器。可以根据 Program 中制定的状态转移规则，决定读写头的具体操作。
通过纸带传输信息，读写头在纸带上移动，每个时刻，机器头从只带上读入一个方格的信息，然后结合自己的内部状态和程序来确定输出的动作，如写入、擦除、返回之前的方格等等，同时更新自己的内部状态。
举一个例子来表述一个 3-symbol 图灵机是如何工作的：一个纸袋上初始的输入是 010, 我们想把它转化为 101，也就是取反。
这张表定义了 Program 中的指令，控制器将按照这个规则来操纵读写头。
计算流程如下所示：
像这种，给定输入，通过一系列操作，得到输出的想法，在现在看来已经习以为常，因为我们日常生活中接触的机器都是这么个意思，但是在 1936 年是有划时代的意义，图灵机证明了可计算理论并给出了具体的实现方式，即可计算的极限就是机器能够计算的极限，可以将问题转化为可计算问题来交给机器解决。
图灵认为这样的一台机器就能模拟人类所能进行的任何计算过程。
三、图灵测试
关于图灵测试则发表于图灵的另一篇论文中《ComputingMachinery and Intelligence （计算机器与智能）》，也正是这篇论文奠定了图灵作为人工智能之父的地位，这篇论文着重回答一个问题：机器能思考吗？
图灵巧妙的避开思维、意识等哲学上的探讨，重新设计了一个试验来考量这个问题，图灵管他叫模仿游戏，也就是那部纪念图灵的电影名字，这个就是图灵测试。在很长一段时间内, 这一测试都是较为公认的人工智能判断标准。
图灵测试，指测试者与被测试者（一个人和一台机器）隔开的情况下，通过一些装置（如键盘）向被测试者随意提问。进行多次测试后，如果机器让平均每个参与者做出超过30%的误判，那么这台机器就通过了测试，并被认为具有人类智能。
2020.7 人工智能公司 openAI 推出了新一代语言模型：GPT-3。
这是一个已经训练好，存在云端的一个人工智能模型，他可以生成网页、图表、代码、文本以及推理，还能应对程序员面试、回复邮件、写积分表达式、回答物理问题。
例如，输入“创建一个长得像西瓜的按钮”，就生成了下图中绿皮红瓢的原型按钮。
输入“史上最丑emoji”，应用给出的答案竟然是它~😂
image.png
输入“自2020年来有多少用户注册”，就能得到相应的 SQL 代码，可以看到，代码将时间起点设为 2020-01-01，刚好对应“自2020年来”。
输入“创建一个带照相机图标、Photo 为标题、信息图标的导航栏，在应用中发送照片，每张照片有一个用户图标、一个点赞图标，和一个聊天泡泡图标”，就能生成下图中的应用界面，它实现了所有的需求。
如果让 GPT-3 去面试，以下这个应用就展示了一个面试对话，虽然面试最后挂了~
人：你好，你是谁？
AI：我是由OpenAI创建的AI。今天如何为您服务？
人：准备好了吗？我们将做一个Ruby编码面试。
AI：好的！开始吧。
人员：编写代码以反转数组。
AI：我可以使用一种已经存在的方法吗？
人：好的。
AI：Array.reverse
人：很好。如果你有一个名为“foo”的数组，并且也想打印出数组，但其元素反转了，要如何做呢？
AI：我会在“ foo”上调用Array.reverse。
人：你还必须打印它，这时要怎么写代码？
AI：好的。print（foo.reverse）
GPT-3 的基础还是深度神经网络，他有 1750 亿个参数，喂给 GPT-3 的文本数据约 45TB，基本上，网络上能找到的书籍、文章、文本，所有算得上是文本的数据都喂进去了，但是仍然没通过图灵测试。
五个里面答对了四个，但当提出网络上没出现过的问题，GPT3就失灵了！因为正常人不会去比较铅笔和烤箱的重量。
问几个「超越现实」的问题，GPT-3 居然可以进行正常的交谈，它不会说「等一下... ... 你的问题是胡说八道。」它也不知道怎么说「我不知道」，你问一些天马行空的问题，它就开启「尬聊」模式，图灵测试fail了。
四、停机问题
对于前文提到的“是不是所有的问题都是可计算的？”
图灵提出了图灵机的构想，但有一个问题却是图灵机无法解决，那就是停机问题。
就是程序写好开始运行后，等了半天毫无反应，既没有报错，又没有停止。
出现这种情况，一般有两种成因。
一是程序运行的时间的确比较耗时，导致机器好像毫无反应。如果是这种情况，很好解决，只要增加运行中的屏幕提示，比如打印某个变量的状态或计算某种进度即可。
但另一种情况会比较麻烦，就是程序执行陷入了死循环，永不停止。如果是这样，那么就必须跟踪查找死循环发生的位置并修改相应程序代码。
停机问题就是把一段代码作为字符串序列输入到一个判断程序中，判断该代码可不以在有限时间内完成计算停止。这就是停机判定问题。
void f(char *t)
其中 t 是输入, 我用一个字符串表示任意输入。停机问题是指对给定任意的一个函数 f 和输入 t, 判断 f 对 t 是否会永远运行下去; 如果程序的运行时间是有限长的, 我们称 f 对 t 停机。
程序员们都期望能够有大牛发明一个判断程序，来提前判断死循环是否会在程序中出现。
遗憾的是, 不存在这样的一个工具使得其能判断任意 f 的停机问题, 即停机问题不可判定。
以下我们用反证法证明这个断言。假设存在这样的一个函数可用于判断停机问题：
bool halts(char *f, char *t)
当 f 对 t 停机时, halts(f, t) 返回 true;
当 f 对 t 不停机, halts(f, t) 返回 false。
我们再构造这样一个函数：
void modified_halts(char *f) {
if (halts(f, f)) { // 如果停机
while (true) { } // 死循环
} else { // 如果不停机
return; // 停机
}
}
如果把 modified_halts 当作 halts 的输入会怎样呢？
halts(modified_halts, modified_halts)
如果 halts 认为会停机，也就是返回 true，那么 modified_halts 程序会死循环，也就是不会停机；而 halts 认为不会停机，也就是返回 false，那么 modified_halts 程序会停机。
这就陷入了矛盾和悖论，也就证明了停机程序是不存在的。
简单的说，「停机问题」说明了现代计算机并不是无所不能的。实际上，现实中与「停机问题」一样是现代计算机「不可解」的问题还有很多，比如所有「判断一个程序是否会在某输入下怎么样？」的算法、Hilbert 第十问题等等。
五、Rice（莱斯）定理
通过停机问题，可以感觉到只要是一个判定问题，就可以套用上面的方法，来反证这个框架是不可判定的，Rice定理对上面情况作了总结：
递归可枚举语言的所有非平凡（non-trival）性质都是不可判定的。
咱们一点一点翻译成人话：
递归可枚举语言，是也叫做部分可判定语言或图灵可识别语言的形式语言类型，这里我们简单的理解为常用C、C++、Java 等语言就好了。
何谓非平凡的性质？平凡性质就是所有程序都有的，或者都没有的性质。那么非平凡性质，就是仅某些程序才有，某些没有。比如程序有没有内存泄漏，或者程序可不可以被优化。
何谓不可判定？说白了就是，找不到一个完美的算法，来判定程序是否有某个性质。
举个例子：
比如计算圆面积的公式是一个函数，那么我想写一个自动判断程序，判断张三的程序是否正确计算了这个圆面积。结论是：这样的判断程序是不存在的。
这可能和现实的感觉不一样，你会感觉好像有这样的程序，其实不是，现实中的确可以写出来，但写出来的程序会有误判，因为这是一个不可计算问题，现实的解决方案只能做到近似。
现实生活中有非常多的具有判别功能的程序，存在着误报和漏报，因为它们解决的都是不可计算问题，这些程序做的，只是权衡误报率和漏报率，根据需要给出一个较优解。
所以，关于静态分析，引用 Rice 定理：完全准确的静态分析程序是不存在的，或者说普适的静态分析算法，静态分析工具是不存在的。
世界上不存在一个程序，可以检测任何程序 P 是否具有某个安全漏洞。
世界上不存在一个程序，可以检测任何程序 P 是否进入了某个 if 分支。
世界上不存在一个程序，可以检测任何程序 P 是否...
由于程序的任何非平凡性质都是不可判定的，所以静态分析算法只能给出源程序某些性质的不完全或不精确的解。
网友评论