本书介绍计算模型理论，包括计算的对象、本质、定义、分类、表达、逻辑和机械实现方法，以及计算模型的典型应用。
全书共分为6章。第1章介绍计算的对象和本质，将离散变量作为图灵计算（离散变量计算）的对象，将其逻辑确定性和机械能行可计算性作为图灵计算的本质；第2章介绍可计算函数——递归函数；第3章介绍计算机的数学原理；第4章介绍语言的计算；第5章介绍判定问题的可计算性；第6章介绍计算模型的典型应用。
本书是计算理论（计算模型、形式语言与自动机）、计算机科学技术史、逻辑学、语言学、数学、哲学的交叉研究，也是通过浅显易懂的讲解方式进行计算机核心理论教学的尝试。作者力图为计算机相关人员提供一个计算的本质特征的“灵魂”描述及其通俗解释，以使得计算机软硬件的所有任务、过程，特别是软件的表达与执行归结为数学原理和逻辑本质。
本书适合作为高等院校计算机、通信、自动化、软件工程、信息管理、数理逻辑与数学基础、生成转换语言学等专业本科生和研究生的教材。同时，由于本书内容深入浅出，能够被仅具有基本数学知识的人读懂，因此也可供对计算机理论感兴趣的广大科技工作者参考。
1、深入探讨图灵可计算性的数学原理，将图灵计算模型具体、详尽、直观地解释为递归函数，从而使读者彻悟作为一个物理过程的图灵计算其数学“灵魂”------离散计算的核心思想和原理----是什么。
2、对图灵计算模型的数学函数-----递归函数进行了综述和分类，使得读者能够从历史和逻辑的视野洞悉递归函数的发展脉络和形式结构及其逻辑分类。
3、以深入浅出的方式讲解和评介计算的基本原理和方法，用了较多的图示，直观易懂；关键问题提供了作者自己编纂的例题，形象而浅显。
4、将跨学科的分割的一体化内容进行了融汇贯通，主要地将计算的数学哲学、数理逻辑、计算与符号推导的形式语言学（乔姆斯基文法）融入了计算理论，使读者能够全方位了解知识的整体性和不同侧面。
本书讲解计算的主要理论和方法，期望为读者解析如下内容:
（1） 什么是计算？如何概括并形式化地表示计算?
（2） 计算的种类有哪些？它们的核心特征是什么?
（3） 如果符号是被计算的对象和结果，那么，作为符号的语言是可以被计算出来的吗?
（4） 如何通过计算判定一个问题的答案的对错?
（5） 计算模型——作为对计算本质的描述和抽象——的典型应用（模型的实例化）是什么?
大致上说，本书内容相当于“计算模型”“形式语言与自动机理论”“计算与语言”的课程内容，是这些课程的基础、核心知识及其原理、方法和效果的形象和通俗的解释。
作者认为，当前“计算模型”“形式语言与自动机理论”“计算与语言”等课程的教学存在一些问题，这些问题集中在以下两个方面。
（1） 对于计算模型，语言学和计算机科学割裂了同一或密切相关的知识。在语言学领域，乔姆斯基语法是被广为接受的，但是这些语言学的研究很少介绍这些语法与计算机的本质、图灵机的运行之间的关系；同样，一个计算机专业的人可以知晓自动机的类型，却缺少对乔姆斯基语法的特征和分析方法的了解。这种学科分割的状况可以解释我国语言学和计算机科学技术学科发展的一些问题。语言学界承认，近百年来在语言学核心理论、有重要影响力的理论和方法方面，我国贡献很少。我们缺少像索绪尔、乔姆斯基、蒙太古等人的语言学理论那样的开创性成果，而实际上这些语言成果的原理都是在描述可计算性，通俗地说是“计算”相关的或计算本质的语言学描述。同样，在计算机科学技术领域，一个程序员会为自己熟练运用一门语言如Java而自豪，但是其中很多人对Java语法的表示却知晓不多，甚至不知道乔姆斯基语法为何物。我国的计算机应用似乎走在了世界的前列，但这些基本上是计算机某种语言的应用，却很少研制出一门计算机编程语言——那么多层出不穷的计算机编程语言: C，C++,Python,Prolog,Mathematica等都是计算理论的原创国家研制的，它的底层除了那些技术手段以外，其灵魂基本上是逻辑及可计算语言学的原理。一个学习语言学的人可能会对计算机程序员感到很陌生，而后者可能感觉前者是个文科领域的异类，但是计算机界的人士似乎并不思考为什么只能应用别人研制的编程语言，自己却不能研制一门语言。
[1]计算理论解析[1]前言〖2〗（2） 对于图灵机本质的介绍不够深入。计算模型（图灵计算、形式理论与自动机等）课程基本上只有部分硕士研究生才会去学习，那么多计算机科学技术的本科生直到毕业也不知道图灵计算为何物——自己学的做的、自己的“饭碗”，甚至思维都是图灵计算，但就是不知道什么是“图灵计算”！这样的程序员就像一个泥瓦匠，楼房盖完了也不知如何设计房屋，完全处于工匠地位。这种状况的根源是在专业教学中缺乏对图灵机原理的充分介绍和讲解。
虽然不敢说本书能在多大程度上解决上述问题，但还是力图在架设计算机科学技术与其他学科的桥梁方面有所禆益。
概言之，计算理论、计算模型课程，重要的不仅是介绍一些个别技术，还应该被当作计算的核心构架而被提纲挈领，应该作为计算的灵魂而被透彻理解，应该是科学史中的人类计算思想发展的脉络而被哲学家导引并被看穿。
本书力图体现出如下特点。
（1） 注重知识的系统性。深入全面介绍概念的背景、本意、关联关系，将知识放置在数学、逻辑学、计算机科学技术、语言学、科学技术史的背景下统一介绍，力图克服知识因不同学科划分而被割裂的常见弊端。
例如，对递归函数的介绍，从递归函数的源头——斯克伦、希尔伯特的定义开始介绍，将逻辑、数学、数学史、计算哲学统一起来，有助于让读者理解计算的“灵魂”，能够使千变万化的计算有一个根本的概念和历史的渊源图景，这是在类似课程的教科书里不多见的。
（2） 侧重介绍图灵机是如何表示和实现递归运算的，详细地说明了图灵计算的本质是递归计算，将图灵机表述为递归函数，图示了计算机对图灵机的模拟模式。这些内容侧重图灵机的“灵魂”，即图灵机实现递归函数的逻辑表示。
（3） 提出自己的独立观点，不只是介绍知识内容和进展。
例如，本书对于递归函数的分类，提出了一个递归函数分类表，在递归函数的概念内涵解释上，对我国学术界将“一般递归函数”解释为μ全递归函数，即将一般递归函数解释为μ部分递归函数的子类的观点提出了不同意见。本书认为“一般递归函数”就是广义递归函数，它是递归函数的最广义的递归函数类。
再如，本书在计算分类上提出了图灵计算包括枚举、语言识别、函数判定三类，并给出其各自的属性特征。
（4） 突出重点，侧重介绍知识主干，舍弃一些衍生的、枝节的知识。
（5） 力图深入浅出，特别注意用图示直观展示内容。
（6） 附有较多例题，便于理解和实践相关问题和方法。这些例题绝大多数是作者自己编纂、提出和设计的。
尽管如此，本书仍难免存在疏漏和不足，欢迎读者指正!
作者张寅生
2016年1月
第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
新书资讯