Обчислюване число

У математиці обчислюване (або рекурсивне) число — це число, яке може бути обчислене з будь-якою заданою точністю за допомогою алгоритму (для комплексних чисел повинні бути обчислювані і дійсна, і уявна частини).

Вони також відомі як рекурсивні числа, ефективні числа, обчислювані дійсні числа або рекурсивні дійсні числа. Поняття обчислюваного дійсного числа ввів 1912 року Еміль Борель, скориставшись інтуїтивним поняттям обчислюваності, доступним на той час.

Еквівалентні визначення можна надати за допомогою μ-рекурсивних функцій, машин Тюрінга або λ-числення як формальне представлення алгоритмів. Обчислювані числа утворюють дійсне замкнуте поле і можуть використовуватися замість дійсних чисел для багатьох, але не для всіх, математичних цілей.^{[джерело?]}

Число, що не обчислюється, називається необчислюваним (прикладом необчислюваного числа є константа Хайтіна в проблемі зупинки).

Будь-яке алгебричне число (а отже, будь-яке раціональне і тим більше будь-яке ціле число) є обчислюваним. Будь-який елемент кільця періодів (що включає число π і багато інших трансцендентних числа) є обчислюваним. Будь-яке обчислюване число є арифметичним.

Множина всіх обчислюваних чисел є зліченною множиною, а множина всіх необчислюваних чисел — незліченною. Множина всіх обчислюваних чисел (як і множина всіх необчислюваних чисел) щільна в $\mathbb {R}$ і в $\mathbb {C} .$

Порядок на множині обчислюваних дійсних чисел ізоморфний порядку на множині раціональних чисел.

Визначення

Дійсне число $x$ називають обчислюваним, якщо існує алгоритм, який дозволяє для кожного $n\in P$ обчислити за скінченне число кроків двійковий дріб $a={\frac {k}{2^{r}}},\ k\in \mathbb {Z} ,\ r\in \mathbb {N}$, такий, що $|x-a|<2^{-n}$.

Властивості

• Сума, різниця та добуток обчислюваних чисел є обчислюваними.
• Границя послідовності обчислюваних раціональних чисел не обов'язково є обчислюваним числом (але завжди є тюрінговим стрибком)
• Існує взаємно однозначна відповідність між обчислюваними підмножинами $S\subset P$ та обчислюваними дійсними числами $x\in [0,1]$.

Див. також

• Алгоритмічна розв'язність
• Конструктивне число
• Степінь Тюрінга

Література

• 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. 55 (4): 303—316. doi:10.4064/ba55-4-2.
• Lambov, Branimir (5 квітня 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.
• Rice, Henry Gordon (1954). Recursive real numbers. Proceedings of the American Mathematical Society. 5 (5): 784—791. doi:10.1090/S0002-9939-1954-0063328-5. JSTOR 2031867.
• Specker, E. (1949). Nicht konstruktiv beweisbare Sätze der Analysis (PDF). Journal of Symbolic Logic. 14 (3): 145—158. doi:10.2307/2267043. JSTOR 2267043. S2CID 11382421. Архів (PDF) оригіналу за 21 липня 2018.
• Turing, A. M. (1936). On Computable Numbers, with an Application to the Entscheidungsproblem. Proceedings of the London Mathematical Society. Series 2опубліковано 1937. 42 (1): 230—65. doi:10.1112/plms/s2-42.1.230. S2CID 73712.
  Turing, A. M. (1938). On Computable Numbers, with an Application to the Entscheidungsproblem: A correction. Proceedings of the London Mathematical Society. Series 2опубліковано 1937. 43 (6): 544—6. doi:10.1112/plms/s2-43.6.544. — у цій праці введено обчислювані числа (і а-машини Тьюрінга); у визначенні обчислюваних чисел використано нескінченні десяткові послідовності.
• van der Hoeven, Joris (2006). Computations with effective real numbers. Theoretical Computer Science. 351 (1): 52—60. doi:10.1016/j.tcs.2005.09.060.
• Aberth, Oliver (1968). Analysis in the Computable Number Field. Journal of the Association for Computing Machinery. 15 (2): 276—299. doi:10.1145/321450.321460. S2CID 18135005. 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.
• Stoltenberg-Hansen, V.; Tucker, J.V. (1999). Computable Rings and Fields. У Griffor, E.R. (ред.). Handbook of Computability Theory. Elsevier. с. 363—448. ISBN 978-0-08-053304-9.
• Weihrauch, Klaus (2000). Computable analysis. Texts in Theoretical Computer Science. Springer. ISBN 3-540-66817-9. — у § 1.3.2 введено визначення вкладених послідовностей відрізків, що збігаються до синглетного дійсного. Інші представлення обговорюються в § 4.1.
• Weihrauch, Klaus (1995). A simple introduction to computable analysis. Fernuniv., Fachbereich Informatik.