Izračunljivo število

V matematiki so izračunljiva števila realna števila, ki se lahko izračunajo do želene natančnosti s končnim algoritmom. Imenujejo se tudi rekurzivna števila, efektivna števila (vanDerHoeven) ali izračunljiva realna števila ali rekurzivna realna števila.

π se lahko izračuna z veliko natančnostjo. Prikazana natančnost 10.000 decimalk.

Ekvivalentne definicije se lahko podajo z uporabo μ-rekurzivnih funkcij, Turingovih strojev ali λ-analize kot formalne predstavitve algoritmov. Izračunljiva števila oblikujejo realni zaprti prostor in se lahko uporabljajo namesto realnih števil za veliko, a ne vseh matematičnih namenov.

Glej tudi

• Definirano število
• Pol-izračunljivo število
• Trans-izračunski problem

Viri

• Aberth, Oliver (1968). »Analysis in the Computable Number Field«. Journal of the Association for Computing Machinery. Zv. 15, št. 2. str. 276–299. doi:10.1145/321450.321460. This paper describes the development of the calculus over the computable number field.
• Bishop, Errett; Bridges, Douglas (1985). Constructive Analysis. Springer. ISBN 0-387-15066-8.
• Bridges, Douglas; Richman, Fred (1987). Varieties of Constructive Mathematics. Cambridge University Press. ISBN 978-0-521-31802-0.
• Hirst, Jeffry L. (2007). »Representations of reals in reverse mathematics«. Bulletin of the Polish Academy of Sciences, Mathematics. Zv. 55, št. 4. str. 303–316. doi:10.4064/ba55-4-2.
• Lambov, Branimir (5. april 2015). »RealLib«. GitHub.
• Minsky, Marvin (1967). »9. The Computable Real Numbers«. Computation: Finite and Infinite Machines. Prentice-Hall. ISBN 0-13-165563-9. OCLC 0131655639. — expands on the topics of this article.
• Rice, Henry Gordon (1954). »Recursive real numbers«. Proceedings of the American Mathematical Society. Zv. 5, št. 5. str. 784–791. JSTOR 2031867.
• Specker, E. (1949). »Nicht konstruktiv beweisbare Sätze der Analysis« (PDF). Journal of Symbolic Logic. Zv. 14, št. 3. str. 145–158. JSTOR 2267043.
• Turing, A.M. (1936). »On Computable Numbers, with an Application to the Entscheidungsproblem«. 2. Zv. 42, št. 1 (objavljeno 1937). str. 230–65. doi:10.1112/plms/s2-42.1.230. {{navedi revijo}}: Sklic magazine potrebuje|magazine= (pomoč)
  Turing, A.M. (1938). »On Computable Numbers, with an Application to the Entscheidungsproblem: A correction«. 2. Zv. 43, št. 6 (objavljeno 1937). str. 544–6. doi:10.1112/plms/s2-43.6.544. {{navedi revijo}}: Sklic magazine potrebuje|magazine= (pomoč) Computable numbers (and Turing's a-machines) were introduced in this paper; the definition of computable numbers uses infinite decimal sequences.
• Weihrauch, Klaus (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.
• Weihrauch, Klaus (1995). A simple introduction to computable analysis. Fernuniv., Fachbereich Informatik.
• Stoltenberg-Hansen, V.; Tucker, J.V. (1999). »Computable Rings and Fields«. V Griffor, E.R. (ur.). Handbook of Computability Theory. Elsevier. str. 363–448. ISBN 978-0-08-053304-9.
• vanDerHoeven, Computations with effective real numbersPredloga:Full citation needed