可计算函数 pdf epub mobi txt 电子书下载 2025

简体网页||繁体网页

☆☆☆☆☆

[俄罗斯] 沈（A.Shen），[俄罗斯] 韦列夏金（N.K.Vereshchagin）著，陈光还译

图书标签:

可计算性理论
递归论
图灵机
lambda演算
形式语言
算法
计算复杂性
数学逻辑
理论计算机科学
程序设计语言

下载链接在页面底部

facebook linkedin mastodon messenger pinterest reddit telegram twitter viber vkontakte whatsapp 复制链接

想要找书就要到图书大百科

book.teaonline.club

立刻按 ctrl+D收藏本页

你会得到大惊喜!!

出版社：高等教育出版社

ISBN：9787040386929

版次：1

商品编码：11398662

包装：平装

丛书名：大学生数学图书馆

开本：32开

出版时间：2014-01-01

用纸：胶版纸

页数：159

字数：140000

正文语种：中文

具体描述

内容简介

　　这本生动、简洁的书基于作者在莫斯科大学力学数学系的本科生课程讲义，涵盖了计算的一般理论的基本概念。《可计算函数》从可计算函数的定义和一个算法开始，讨论了可判定性、可数性、通用函数、编号系统及其性质、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定理：胜出条件
……
第八章算术分层
第九章 Turing机
第十章可计算函数的算术化
第十一章递归函数
参考文献
人名表
索引

精彩书摘

　　Turing机可以计算什么样的函数呢？根据Turing论点，任何可计算函数都是Turing可计算的。自然地，这句话的含义依赖于对术语“可计算函数”的理解。如果是按照模糊的直觉意义来理解f就像“一个函数可被算法地求值”即“由完全清晰的规则”或某些类似的东西），那么Turing论点的严格证明当然是不可能的。我们能说的只有一件事，从Euclid到Knuth的许多世纪以来从未遇到过一个算法不能转译为Turing机程序的，然而，下面我们还是要给出一个论证（虽然不太有说服力）。如果把Turing论点中的“可计算”当成“用Pascal程序可计算”，并且设想Pascal程序的语法和语义都定义好了，那么Turing论点就是一个可证明成立或不成立的明确的命题了。当然这样的证明必须建立在Pascal的语法和语义的形式化描述之上，而这从来没有人做过，然而，这类证明的简化的计算模型实际上曾经给出过，它们近似于冗长程序的正确性证明，很少人愿意去写，更少人愿意去读它。
　　最后，我们来介绍上面提到的支持任何可计算函数的Turing机可计算性的非形式化论证，假设你（或者任何其他人）能对给定的变量计算某个函数f.我们来描述模拟你的工作的Turing机。
　　你自然要用纸和铅笔（连同橡皮擦），因为能记住的信息总量是很有限的，假设你写在同样大小的纸页上：有两堆纸页，分别放在你当前页的两边；在当前页做完后，可以把它放到其中一堆上，再从另一堆顶上取下一个工作页。
　　……