全国大中专教材网络采选系统

推荐纸质教材推荐数字资源

可计算函数

￥35.00定价

作者： A.Shen，N.K.Vereshchagin著

译者：陈光还译；

出版时间：2014年1月

出版社：高等教育出版社

以下为《可计算函数》的配套数字资源，这些资源在您购买图书后将免费附送给您：

关闭

基本信息评价

出版社：高等教育出版社
ISBN：9787040386929
版次：1版
图书编号：75171
本季征订号：0045155457-0
开本：16开
出版时间：2014年1月
千字：200
页数：159
学科分类1：理学
学科分类2：数学
中图分类编号：O174.1
适用专业：数学类
适用分级：研究生、本科

内容简介

这本生动、简洁的书基于作者在莫斯科大学力学数学系的本科生课程讲义，涵盖了计算的一般理论的基本概念。沈、韦列夏金著，陈光还译的《可计算函数》从可计算函数的定义和一个算法开始，讨论了可判定性、可数性、通用函数、编号系统及其性质、m-完全性、不动点定理、算术分层、oracle计算、不可判定性的度。作者还介绍了一些特殊的函数模型，如Turing机和递归函数。　　《可计算函数》可供数学和计算机专业的本科生阅读，也可供所有希望学习计算的一般理论的基础知识的数学家和程序员使用。

《大学生数学图书馆》丛书序

引言

第一章可计算函数、可判定集与可数集

1.可计算函数

2.可判定集

3.可数集

4.可数集与可判定集

5.可数性与可计算性

第二章通用函数与不可判定性

1.通用函数

2.对角构造

3.可数的不可判定集

4.可数的不可分集

5.单集：Post构造

第三章编号与运算

1.Godel通用函数

2.可计算函数的可计算序列

3.Godel通用集

第四章 Godel编号系统的性质

1.编号集

2.旧函数的新编号

3.Godel编号系统的同构

4.函数的可数性

第五章不动点定理

1.不动点与等价关系

2.打印程序文本的程序

3.系统的技巧：另一个证明

4.几点附注

第六章 m-可约性与可数集的性质

1.m-可约性

2.m-完全集

3.m-完全性与有效不可数性

4.m-完全集的同构

5.产生集

6.不可分集的对

第七章 Oracle计算

1.Oracle机

2.相对可计算性：等价描述

3.相对化

4.0'-计算

5.不可比集

6.Friedberg-Muchnik定理：构造的一般方案

7.Friedberg-Muchnik定理：胜出条件

8.niedberg—Muchnik定理：优先方法

第八章算术分层

1.类∑n和Ⅱn

2.∑n和Ⅱn中的通用集

3.跳跃运算

4.分层中集的分类

第九章 Turing机

1.简单的可计算模型：需要它们做什么

2.Turing机：定义

3.Turing机：讨论

4.字问题

5.Uuring机的模拟

6.Thue系统

7.半群、生成元和关系

第十章可计算函数的算术化

1.有限个变量的程序

2.Turing机和程序

3.可计算函数是可算术化的

4.Tarski定理和Godel定理

5.Tarski定理和Godel定理的直接证明

6.算术分层和量词交换数

第十一章递归函数

1.原始递归函数

2.原始递归函数的例

3.原始递归集

4.递归的其他形式

5.Turing机和原始递归函数

6.部分递归函数

7.Oracle可计算性

8.生长率的估计、Ackermann函数

参考文献

人名表

索引