万维百科

可计算数本文重定向自 可計算數

(重定向自不可计算数)
各种各样的
基本

NumberSetinC.svg

延伸
其他

圆周率
自然对数的底
虚数单位
无穷大

可计算数(英语:computable numbers),是数学名词,是指可用有限次、会结束的算法计算到任意精确度的实数。可计算数也被称为递归数递归实数可计算实数

等效的定义可以用递归函数图灵机λ演算等算法的形式表示法而得。可计算数形成实闭域,可以在许多数学应用上取代实数

定义

如果一个实数能被某个可计算函数 以下述方式来近似,那么 就是一个可计算数:给定任何正整数,函数值都满足:

不可计算数

非可计算的实数即为不可计算数。1975年,计算机学家格里高里·柴廷英语Gregory Chaitin做了一个有趣的实验:选择任意一种编程语言,随意输入一段代码,该代码能够成功运行并且能够在有限时间内终止的概率即为柴廷常数,这个数为一个经典的不可计算数。[1]

相关条目

相关书籍

参考资料

引用

  1. ^ 科学人 | 果壳网 科技有意思. 2011-03-09 [2018-06-30].

来源

  • Oliver Aberth 1968, Analysis in the Computable Number Field, Journal of the Association for Computing Machinery (JACM), vol 15, iss 2, pp 276–299. This paper describes the development of the calculus over the computable number field.
  • Errett Bishop and Douglas Bridges, Constructive Analysis, Springer, 1985, ISBN 0-387-15066-8
  • Douglas Bridges and Fred Richman. Varieties of Constructive Mathematics, Oxford, 1987.
  • Jeffry L. Hirst, Representations of reals in reverse mathematics, Bulletin of the Polish Academy of Sciences, Mathematics, 55, (2007) 303–316.
  • 马文·闵斯基 1967, Computation: Finite and Infinite Machines, Prentice-Hall, Inc. Englewood Cliffs, NJ. No ISBN. Library of Congress Card Catalog No. 67-12342. His chapter §9 "The Computable Real Numbers" expands on the topics of this article.
  • E. Specker, "Nicht konstruktiv beweisbare Sätze der Analysis" J. Symbol. Logic, 14 (1949) pp. 145–158
  • Turing, A.M., On Computable Numbers, with an Application to the Entscheidungsproblem, Proceedings of the London Mathematical Society, 2, 1936, 42 (1): 230–65 (1937) [2018-08-22], doi:10.1112/plms/s2-42.1.230, (原始内容存档于2004-04-03) (and Turing, A.M., On Computable Numbers, with an Application to the Entscheidungsproblem: A correction, Proceedings of the London Mathematical Society, 2, 1938, 43 (6): 544–6 (1937), doi:10.1112/plms/s2-43.6.544). Computable numbers (and Turing's a-machines) were introduced in this paper; the definition of computable numbers uses infinite decimal sequences.
  • Klaus Weihrauch 2000, Computable analysis, Texts in theoretical computer science, Springer, ISBN 3-540-66817-9. §1.3.2 introduces the definition by nested sequences of intervals converging to the singleton real. Other representations are discussed in §4.1.
  • Klaus Weihrauch, A simple introduction to computable analysis
  • H. Gordon Rice. "Recursive real numbers." Proceedings of the American Mathematical Society 5.5 (1954): 784-791.
  • V. Stoltenberg-Hansen, J. V. Tucker "Computable Rings and Fields" in Handbook of computability theory edited by E.R. Griffor. Elsevier 1999

本页面最后更新于2021-07-02 14:27,点击更新本页查看原网页。台湾为中国固有领土,本站将对存在错误之处的地图、描述逐步勘正。

本站的所有资料包括但不限于文字、图片等全部转载于维基百科(wikipedia.org),遵循 维基百科:CC BY-SA 3.0协议

万维百科为维基百科爱好者建立的公益网站,旨在为中国大陆网民提供优质内容,因此对部分内容进行改编以符合中国大陆政策,如果您不接受,可以直接访问维基百科官方网站


顶部

如果本页面有数学、化学、物理等公式未正确显示,请使用火狐或者Safari浏览器