logo资料库

可计算性与不可解性 pdf 中文影印版.pdf

发布时间：2022-06-08 发布人：admin 分类：说明书 资料大小：6.42M 资料格式：pdf 举报 版权申诉
第1页 / 共291页
第2页 / 共291页
第3页 / 共291页
第4页 / 共291页
第5页 / 共291页
第6页 / 共291页
第7页 / 共291页
第8页 / 共291页
资料共291页，剩余部分请下载后查看
    " 可计算性 与 不可解性 E 羹］ M. 戴维斯蕃
    可计算性与不可解性 , 〔美 J M. 戴维斯著 沈私等译 吴允曾校
    ’』 4‘ 内容简介 本书是→本数学系和计算机系研究生教材．第一至丑章为可计算性理论的 基本内容，可作为数学系和计算机科学系大学生教材或参考书．第六至八章为 这一理论在代数、数论及逻辑中的应用。第九至十一章为可计算性理论的专题． 本书也可供有关研究工作者参考。 MARTIN D • .\ VIS Computability and Unsolvability McGRAW-HILL, 1958 可计算性与不可解性 花京大学出版社出版 〈北京大学校内〉 新华书店北京发行所发行 北京大学印盹厂 .fP 刷 787 × 1092 毫米 32开本 9.25 印张 200 千字 1984 年 8 月第一版 1984 年8月第一次印刷 印数， 1-32,000册 统一书号： 134q9•89 定价： 0. 95 元 、 ” , . ·』， . a 』 ta . ’ - 』 E 、 二一一→←一
    . ‘ . F 、 ' 译者前言 本书作者 M. 戴维斯现任美国纽约州立大学计算机科学 系教授，系著名的数理逻辑学者．他骨和 H. Putnam, J. Robinson, Yu. Matijasevic 等三人一起解决了希尔伯特第十 问题． 本书可作为数学系、计算机系研究生教材．全书共分卡 一章．第一章至第五章为可计算性理论的基本内容，也可作为 数学系和计算机科学系大学生教材或参考书 F 第六章至第八 章为这一理论在代数、数论及逻辑中的应用 F 第九章至第卡 一章为可计算性理论的专题． 在此译本即将付印肘，我们看到了此书的第三版（ 1982 年九第三版与前两版的不同之处是增加了附录二“希尔伯 特第十问题是不可解的”，用来取代第七章．有兴趣的读者 可参阅“Hilbert's Tenth Problem Is Unsolvable”(The American Mathematical Monthly, Vol. 80, No.3, March 1973, PP.233-269). 由于译者水平有限，译文中肯定有不少缺点和错误，敬 请读者批评指正． 参加本书翻译的有z 沈扭〈引言、第一章），戴伟长（第 二、卡、十一章｝，董亦我（第三章），陈安捷〈第四、九 草），何自强（第五章），陈进元（第六章），郭世铭（第七 章、附录），宋柔（第八章）．奥允骨桂对．全部 i季稿由半源 草作了文字上的统一处理． 译者 －九八三年八月 I
    序 --E量 本书是可计算性和不可计算性理论的导引，这个理论通 常称为递归因数论，它榜及到解决各种问题的纯机械过程的 存在性．虽然这个理论是纯数学的一个分支，但是，由于它 同某些哲学问题及数学计算理论有关，所以，对于＃数学工 作者来说也是有一定意义的．绝对不可解问题的存在和哥德 尔不完圭性定理，都属于具有哲学意义的可计算性理论的结 果．该理论的另一个结果是通用图林机的存在，这证实了使 用数字计算机的工作者的这样一种信念z 可以构造一台“圣 能的”数字计算机，凡是能在一台可以设想的确定的数字计 算机上进行程序设计的任何问题，都能在这台圭能的机器上 进行程序设计（当然要受时间和存肿容量的限制｝．有时，还 给出这一断言的加强形式E 凡是做得完圣精确的任何事情， 都能在一台垒能数字计算机上进行程序设计．然而，这样的 断言却是错误的．事实上，可计算性理论的基本结果之一 〈即存在＃递归的递归可枚举集合｝，可以解释成如下断言z 可以在给定的计算机上编出一个程序，以致不可能在任何一 台计算机〈或者是那台给定计算机的复制品，或者是另一台 机器〉上编出→个程序，来断定给定的数据是否是那台给定 计算机的输出的一部分．另一个结果（停机问题的不可解 性）可以解释成 z 不可能构造出一个程序来确定任意给出的 程序是否会陷 λ无限循环． 我的目的是使可计算性理论能被不同经历和不同兴趣的 II
    人所接受，所以我已注意〈特别是在前七章中〉不假定读者 有任何特别的数学训练．基于同一理由，对于 McGraw-Hill 图书公司关于把这本书列λ该公司的信息处理和计算机丛书 的建议，我很高兴． 且然本书中边有多少真正的新结果，但专家们也许会在 某些课题的整理和处理上找到一些新东西．特别是以图林机 的概念作为展开的核心．这样做看来是可取的，因为」方 面，图林机的概念具有宦观性，而且图林机同实际的数字计 算机之间存在着相似之处z 另一方面，把对图林机的处理同 哥德尔和 Kleene 的强有力的语法方法结合起来，就可以对 可计算性理论的各个方面一一从 Post 的正规系统到 Kleene 的层共理论一一用统一的方法进行介绍． 本书的部分材料啻用于我编的伊利诺斯大学的研究生敬 材，也骨用于我在伊利诺斯大学控制系统实验室和贝尔电话 公司实验室的一系列讲清．本书的一部分是作者在海军研究 局的资助下，在普林斯顿高级研究所工作时完成的．本书可 以作为数理逻辑或可计算性理论课程的教材或补充教材． 我要戚谢 Donald Kreider 先生， Hilary Ptttnam 教授， Hartley Rogers, Jr. 教授和 Norman Shapiro 博士，他们对 本书提出过许多修正和改进的意见． M. 戴锥斯 . " . . m 一←一 →←一一一一一
    . 、监 . . 专用符号表 这里所注明的是符号被首共引λ处的页码 ( 7 ) ( 7) ( 7) (7) (7) x (.) y (.) z (.) 帽 ξS 帽 ξS RUS …. ( 7) …. ( 7) Rns R …………………………·..………·.··.………·..…………·...·.··.…·· (7) ¢ ….………··....··...··...………...………….….........……..........·.... (8) Re 5 ........•.........................................•........••.••...•............•... (8) Cs("'1 ,…,"'.)…........……………….........…. ••• . . . . .• ••• . .• ••• ••• . . . . .• . . . ( 9 ) p/l,q …………………………………………………………………………( 9) PV 'I. …........………………………………….........….............………( 9) ~ p…………… H …·………………··………………………………………( 9) ~ x （叫 I P(x<•> > ~…………………………………………........………. (10) p (X＼ η ｝〉忡Q(x <•>)…………………………………………………………(11) Cp("'1 ,…,"'.)…. • • • . . . . • • . . . . . • . . . • . . . . . . . • • . • . . . • . • • . . . . • . . . . . • . . . . . . • . . . . . . . • . • • ( 11) z v P(y 川）〉… 却因。 z / \ P(y 川）｝· Y-0 \ / P(y 川））· 1面 •• -· .. 品，』蛐寸W 一』也← 1
    ( \ P(y 川｝〉…. . • q;S;S1q1 . . . . . . . . . . . . • . . . . . . . .......………. . . . . . .……… ω〉 (16) 、 (16) (16) (16} q ;S, R 堕 E ………………………· q;S;L qi …… q,S,q1q 1 ………………· B …....………………·....…………………………………··............... (17} 1 ……………………………………………………………………………(17} a.+P(Z ) ………………“………………………………·………………(18} Res2(a1 )……………………………………....................…….. . . . . •• ( 2 0) • . . . . . . . . • . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . (21) ｛’ 1••2 ，…，第 1 ）….. . . . . . . • . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ( 2 2) ψγ ） (" l ，吨，…， sρ ·..…………………·......................…............ (22) 1Pz(:<)………………………………………………………………………(22) S(:<)…………………………………………………………………………( 26) r~J····················································································(SO} u f <"1•'"2····, ... ) ·············…. . . . . . . . . . . . . . . . . . . • . . ....................……. (31} a~ β （ z) .......…..................……......................…..............….. (38) Re吁（ a 1 ) . ,, .•••... '' . •• ... ••• ''''…….......……………. . . .. . . . . . . . .. . .. (3 9 > 吗？ ν ＂＇ 1 .吨，.... ".) (39} 甲 f Cz) •.•...••• ''' •••••• .......................................... ··•.….........….. (39} B(Z)………………………………………………………………………. (43) z (. ) ...............................................................................….. (44) 皿in,[f(y,x ＜叫） =OJ …·-…………………………………………--…. . (61} N(z )…………… (67} a(%) [ ../ z ]…”……·…… [ :r/y ] …….......... R( .. ,y )……· J(:a:,y)….....……·· K(z )…………… (67) (67) (67) (68) (68) (70) 2 . . . •
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料