Izračunljivo število

Iz Wikipedije, proste enciklopedije
Jump to navigation Jump to search


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

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.

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[uredi | uredi kodo]

Viri[uredi | uredi kodo]

  • Aberth, Oliver (1968). "Analysis in the Computable Number Field". Journal of the Association for Computing Machinery. Vol. 15 no. 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. Vol. 55 no. 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. Vol. 5 no. 5. str. 784–791. JSTOR 2031867.
  • Specker, E. (1949). "Nicht konstruktiv beweisbare Sätze der Analysis" (PDF). Journal of Symbolic Logic. Vol. 14 no. 3. str. 145–158. JSTOR 2267043.
  • Turing, A.M. (1936). "On Computable Numbers, with an Application to the Entscheidungsproblem". 2. Vol. 42 no. 1objavljeno 1937. str. 230–65. doi:10.1112/plms/s2-42.1.230. Navedi magazine zahteva |magazine= (pomoč)
    Turing, A.M. (1938). "On Computable Numbers, with an Application to the Entscheidungsproblem: A correction". 2. Vol. 43 no. 6objavljeno 1937. str. 544–6. doi:10.1112/plms/s2-43.6.544. Navedi magazine zahteva |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