计算机科学与导论 第十七 十八章 计算理论，人工智能

计算理论

17.1 引言

这一章是对计算理论的一个简单的介绍。首先，介绍一种语言，称为简单语言。其次，介绍一种工具，一种称为图灵机的计算机模型，第三我们将证明没有任何程序可以知道另一个程序终止与否。

17.2 简单语言

我们可以仅用3条语句来定义一个语言，它们是:递增语句，递减语句，循环语句

17.3 图灵机

图灵机由三部分组成:磁带，控制器和读写头。
1.磁带
尽管现代计算机中使用的随机存储设备容量是有限的，但我们假定图灵机中的内存是无限的。磁带任何时候只能保存一些列顺序的字符，该字符来自计算机所能接收的字符集中。

2 读/写头
读写头在任何时刻总是指向磁带上的一个符号，我们称这个符号为当前符号，读/写头 每次在磁带上读写一个符号。每读写完一次后，他向左移，向右移。读，写，和移动都是在控制器指令下进行的。
3 控制器
控制器是理论上功能作用类似现代计算机中中央处理单元(cpu)的一个部件，它是一个有限状态自动机，即该机器有预定的有限个状态并能根据输入从一个状态转移到另一个状态，但任何时候他只能处于这些状态中的一种。

邱奇 -图灵 论题

如果存在一个能完成一个符号操纵任务的算法，那么也存在一台完成这个任务的图灵机。
注意这只是论题，不是定理。定理可以在数学上得到证明，但论题不能。虽然这个论题可能永远得不到证明，但有些强有力的论断在支持它。首先，尚未发现有图灵机不能模拟的算法；其次，所有在数学上已经得到证明的计算机模型都与图灵机模型等价，这个论断是得到证明。

人工智能

引言

18.1.1 什么是人工智能

人工智能是对程序系统的研究，该程序系统在一定程度上能模仿人类的活动，如感知，思考。学习和反应

18.1.2 智能体

智能体可以分为俩大类:软件智能体和物理智能体

1.软件智能体
软件智能体是一组用来完成特殊任务的程序。例如，有些只能系统用来整理电子邮件，能检查收到的邮件的内容，然后把它们归入不同的类别中。另外一个软件智能体的例子是搜索引擎。

2.物理智能体
物理智能体是一个用来完成各项任务的可编程系统。简单的机器人可以用在制造行业。

18.1.3 编程语言

虽然有些通用能用来编写智能软件，但有俩种语言是特别为人工智能设计的，它们是:LISP和PROLOG.
1.LISP
LISP 是一种操纵表的编程语言。LISP把数据和程序都当成表，这就意味着LISP程序能改变它自身。这个特性与智能体的理念相吻合。
但是LISP得一个缺点是它的行动迟缓，如果要处理的表比较长，LISP就变得很慢。另一个缺点是它的语法复杂。
2.PROLOG
是一种能建立事实数据库和规则知识库的编程语言。使用PROLOG编程能使用逻辑推理来回答那些可以从知识库中推导出来的问题。但是PROLOG不是效率很高的编程语言，有些复杂问题使用其他语言效率更高。

18.2 知识的表示

如果打算用人工智能体来解决现实世界的一些问题，那么它必须能表示知识。事实被表示成数据结构后就能被存储在计算机中的程序操作。我们描述4种常见的知识表示法，语义网，框架，谓词逻辑和基于规则的系统。

18.2.1 语义网

语义网使用有向图表示知识。有向图由顶点和边构成。语义网用顶点表示概念，用边表示俩个概念的关系。

18.2.2 框架

框架与语义网紧密相关。在语义网中，图用来表示知识，在框架中，数据结构（记录）用来表示相同的知识。与语义网相比框架的一个优点是程序更容易处理框架而不是语义网。
1.对象
语义网中的一个节点变成了一组框架的一个对象，所以一个对象可以定义一个类，子类或者实例。

2.槽
语义网中的边被翻译成槽。槽的名字定义了关系的类型和构成关系的槽的值。

18.2.3 谓词逻辑

命题逻辑，谓词逻辑，超谓词逻辑（高阶逻辑，模态逻辑，时态逻辑，默认逻辑）

18.2.4 基于规则的系统

基于规则的系统使用一组规则来标识知识，这些规则能用来从已知的事实中推导出新的事实。
规则表示当指定条件满足时什么为真。基于规则的数据是一组if …then…语句，它们的形式为 if A then B 或者A->B

其中A为前提，B为结论。
1.组成
一个基于规则的系统由三部分构成:解释器（或推理机），知识库和事实库

（1）知识库
基于规则系统的知识库部分就是规则的数据库。它包含一组预先建立的规则，这些规则能从给定的事实库中得出结论。
（2）事实库
事实库中包含了知识库中的规则要使用的一组条件
（3）解释器
解释器（推理机）是一个处理器或控制器（如一段程序），它把规则和事实组合在一起。解释器有俩种类型:正向推理和反向推理。

18.2 专家系统

专家系统使用前面所讨论的知识表示语言，来执行通常需要人类专家才能完成的任务。

1.用户
用户是使用系统，从所提供的专家经验中获益的实体

2.用户界面
用户界面允许用户与系统交互，用户界面能接收用户的自然语音，然后把它们翻译给系统。

3.推理机
推理机是专家系统的心脏，它使用知识库和事实库推导出要采取的动作。

4.知识库
知识库是基于与相关领域专家的会面而得到的知识的集合

5.事实库
事实库在专家系统中是基于事例的。对于每个事例，用户输入可用的度量的数据进入事实库，推理机为这特殊的事例使用这些数据。

6解释系统
并不是所有专家系统都有解释系统，它用来解释推理机得出的结论的合理性。

7 知识编辑器

并不是所有的专家系统都有知识编辑器，当从领域专家那里获得新的经验时，用知识库编辑器来更新知识库。

18.3 语言理解

机器理解自然语言的任务分成4个连续的步骤:语音识别，语法分析，语义分析，语用分析。

（1）语音识别是第一步就是分析出一句话的各个词
（2）语法分析这一步用来定义单词在句子中时如何组织的。
（3）语义分析就是在句子被语法分析之后抽取出句子的意思
（4）语用分析是用来进一步明确句子的意图和消除歧义。

18.4 搜索

人工智能解决问题的一种技术是搜索。
有俩种常用的搜索方式:蛮力搜索和启发式搜索，蛮力搜索本身又有广度优先和深度优先

18.5 多层神经网络

应用:俩个证明神经网络有用的领域是光学字符识别(OCR)和信用赋值(不同的因素赋予不同的权值去建立信用等级，例如用于贷款申请)