SEP：可计算性与复杂性（一） (5-1)

本文使用 Zhihu On VSCode 创作并发布

SEP:可计算性与复杂度（Computability and Complexity）

*由L. T. F. Kanud of Vihara译出(译： cjy、校： 虎猫(第一节到第三节)， 羽川翼(第四节))

曾载于豆瓣： /note/7850701...

*作者 Neil Immerman (immerman@cs.)是马萨诸塞大学的一位理论计算机科学家，1995年哥德尔奖获得者，描述复杂性(descriptive complexity)理论的主要开发者之一。

*参考文献部分请参原文: plato./entr...

*本文是一篇关于， 图灵机， 丘奇-图灵论题，递归可枚举， 递归函数等关键概念，与计算理论中的可计算性理论及 计算复杂性理论的，简单而优秀的科普。上面给出了有进一步专门词条的超链接，有兴趣的或许可做进一步阅读。

First published Thu Jun 24, 2004; substantive revision Wed Sep 2, 2015

一个数学问题是可计算的(computable)，当其原则上是可由一个计算手段解决的(computing devices)。关于“可计算的”的一些常见同义词是，“可解的(solvable)”，“可判定的(decidable)”，“递归的(recursive)”。希尔伯特相信所有数学问题都是可解的，但是在1930年代，哥德尔，图灵，丘奇，表明事实并不如此。而这里就会有一个广泛的研究与分类是关于，哪些数学问题是可计算的，而哪些不是。另外，根据这个问题的计算量，有一个广泛的分类，将可计算的问题分为到不同的计算复杂性类(computational complexity classes)中，而计算量指，需要多少计算去回答问题的实例，根据于该问题实例的大小。令人惊讶的是，被描绘出的这些分类是如此的清晰，优雅与精确。

目录

•1. What can be computed in principle? Introduction and History

•2. Turing Machines

o2.1 Universal Machines

o2.2 The Halting Problem

o2.3 Computable Functions and Enumerability

o2.4 The Unsolvability of the Halting Problem

•3. Primitive Recursive Functions

o3.1 Recursive Functions

•4. Computational Complexity: Functions Computable in Practice

o4.1 Significance of Complexity

•Bibliography

•Academic Tools

•Other Internet Resources

•Related Entries

1. What can be computed in principle? Introduction and History

数学联邦政治世界观提示您：看后求收藏（同人小说网http://tongren.me），接着再看更方便。