计算理论解析

　　本书介绍计算模型理论，包括计算的对象、本质、定义、分类、表达、逻辑和机械实现方法，以及计算模型的典型应用。全书共分为6章。第1章介绍计算的对象和本质，将离散变量作为图灵计算（离散变量计算）的对象，将其逻辑确定性和机械能行可计算性作为图灵计算的本质；第2章介绍可计算函数——递归函数；第3章介绍计算机的数学原理；第4章介绍语言的计算；第5章介绍判定问题的可计算性；第6章介绍计算模型的典型应用。本书是计算理论（计算模型、形式语言与自动机）、计算机科学技术史、逻辑学、语言学、数学、哲学的交叉研究，也是通过浅显易懂的讲解方式进行计算机核心理论教学的尝试。作者力图为计算机相关人员提供一个计算的本质特征的“灵魂”描述及其通俗解释，以使得计算机软硬件的所有任务、过程，特别是软件的表达与执行归结为数学原理和逻辑本质。本书适合作为高等院校计算机、通信、自动化、软件工程、信息管理、数理逻辑与数学基础、生成转换语言学等专业本科生和研究生的教材。同时，由于本书内容深入浅出，能够被仅具有基本数学知识的人读懂，因此也可供对计算机理论感兴趣的广大科技工作者参考。

暂缺《计算理论解析》作者简介

第1章计算的对象和本质1
参考文献6
第2章可计算函数——递归函数7
2.1分解计算、逐步计算的思想8
2.2原始函数10
2.3递归函数的构造方法11
2.3.1复合方法12
2.3.2递归方法12
2.4递归函数的家族21
2.5递归函数的通俗解释22
参考文献23
第3章计算机的数学原理25
3.1数学运算的基础25
3.2希尔伯特第十个问题及其自动化解决思想28
3.3图灵机原理32
3.4图灵机的局部改进和变形50
3.4.1多带图灵机50
3.4.2图灵机的复合53
3.4.3图灵机参数的限定57
参考文献57
[1]计算理论解析[1]目录〖2〗第4章语言的计算59
4.1图灵计算的分类59
4.2语言的可计算性61
4.3作为枚举器的图灵机69
4.4作为语言识别器（接受器）的图灵机70
4.5图灵机和短语语法72
4.6线性有界自动机与上下文有关语法77
4.7下推自动机与上下文无关语法83
4.8确定型有穷自动机与正则语法86
4.9不确定型有穷自动机与正则语法89
4.10自动机接受的语言94
参考文献95
第5章判定问题的可计算性97
5.1基本概念97
5.2不可判定性问题实例98
5.2.1丢番图方程整数解问题99
5.2.2对角线函数102
5.2.3停机问题104
5.2.4逻辑蕴涵106
5.2.5哥德尔语句G109
参考文献110
第6章计算模型的应用112
6.1计算机模拟图灵机112
6.2语言识别和语法验证115
6.3逻辑推理123
6.4计算复杂性分析133
参考文献139