计算理论导引-行业好书-社会科学-太极之巅书单号

书刊介绍

作品目录

出版者的话
专家指导委员会
译者序
译者简介
第1版前言
第2版前言
第0章绪论
0.1 自动机、可计算性与复杂性
0.2 数学概念和术语
0.3 定义、定理和证明
0.4 证明的类型
练习
问题
习题选解
第一部分自动机与语言
第1章正则语言
1.1 有穷自动机
1.2 非确定性
1.3 正则表达式
1.4 非正则语言
练习
问题
习题选解
第2章上下文无关文法
2.1 上下文无关文法概述
2.2 下推自动机
2.3 非上下文无关语言
练习
问题
习题选解
第二部分可计算性理论
第3章丘奇-图灵论题
3.1 图灵机
3.2 图灵机的变形
3.3 算法的定义
练习
问题
习题选解
第4章可判定性
4.1 可判定性
4.2 停机问题
练习
问题
习题选解
第5章可归约性
5.1 语言理论中的不可判定问题
5.2 一个简单的不可判定问题
5.3 映射可归约性
练习
问题
习题选解
第6章可计算性理论的高级专题
6.1 递归定理
6.2 逻辑理论的可判定性
6.3 图灵可归约性
……
· · · · · ·

精彩摘录

Ignoringthetreestoseetheforestdoesn'tmeanthatoneismoreimportantthantheother-itjustgivesadifferentperspective.

——引自第235页

Wehavecometoaturningpointinthestudyofthetheoryofcomputation.WecontinuetospeakofTuringmachines,butourrealfocusfromnowonisonalgorithms.Thatis,theTuringmachinemerelyservesasaprecisemodelforthedefinitionofalgorithm.WeskipovertheextensivetheoryofTuringmachinesthemselvesanddonotspendmuchtimeonthelow-levelprogrammingofTuringmachines.WeneedonlytobecomfortableenoughwithTuringmachinestobelievethattheycaptureallalgorithms.

——引自章节：TerminologyfordescribingTur