计算理论解析

书籍目录

第1章 计算的对象和本质

第2章 可计算函数——递归函数

2.0 预备知识

2.1 分解计算、逐步计算的思想

2.2 原始函数

2.3 递归函数的构造方法

2.3.1 复合方法

2.3.2 递归方法

2.4 递归函数的家族

2.5 递归函数的通俗解释

第3章 计算机的数学原理

3.1 数学运算的基础

3.2 希尔伯特第十问题及其自动化解决思想

3.3 图灵机原理

3.4 图灵机的局部改进和变形

3.4.1 多带图灵机

3.4.2 图灵机的复合

3.4.3 图灵机参数的限定

第4章 语言的计算

4.1 图灵计算的分类

4.2 语言的可计算性

4.3 作为枚举器的图灵机

4.4 作为语言识别器（接受器）的图灵机

4.5 图灵机和短语语法

4.6 线性有界自动机与上下文有关语法

4.7 下推自动机与上下文无关语法

4.8 确定型有穷自动机与正则语法

4.9 不确定型有穷自动机与正则语法

4.10 自动机接受的语言

第5章 判定问题的可计算性

5.1 基本概念

5.2 不可判定性问题实例

5.2.1 丢番图方程整数解问题

5.2.2 对角线函数

5.2.3 停机问题

5.2.4 逻辑蕴含

5.2.4 哥德尔语句G

第6章 计算模型的应用

6.1 计算机模拟图灵机

6.2 语言识别和语法验证

6.3 逻辑推理

6.4 计算复杂性分析

作者简介

本书介绍计算模型理论，包括计算的对象、本质、定义、分类、表达、逻辑和机械实现方法，以及计算模型的典型应用。

全书共分为6章。第1章介绍计算的对象和本质，将离散变量作为图灵计算（离散变量计算）的对象，将其逻辑确定性和机械能行可计算性作为图灵计算的本质；第2章介绍可计算函数——递归函数；第3章介绍计算机的数学原理；第4章介绍语言的计算；第5章介绍判定问题的可计算性；第6章介绍计算模型的典型应用。

本书是计算理论（计算模型、形式语言与自动机）、计算机科学技术史、逻辑学、语言学、数学、哲学的交叉研究，也是通过浅显易懂的讲解方式进行计算机核心理论教学的尝试。作者力图为计算机相关人员提供一个计算的本质特征的“灵魂”描述及其通俗解释，以使得计算机软硬件的所有任务、过程，特别是软件的表达与执行归结为数学原理和逻辑本质。

本书适合作为高等院校计算机、通信、自动化、软件工程、信息管理、数理逻辑与数学基础、生成转换语言学等专业本科生和研究生的教材。同时，由于本书内容深入浅出，能够被仅具有基本数学知识的人读懂，因此也可供对计算机理论感兴趣的广大科技工作者参考。

 计算理论解析下载