Перегляд вихідного коду сторінки Обчислюване число

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

Вони також відомі як '''рекурсивні числа''',<ref>{{Cite book
|url=https://eudml.org/doc/268535
|title=Computable analysis
|last=Mazur
|first=Stanisław
|authorlink1=Станіслав Мазур
|year=1963
|editor-last=Grzegorczyk
|editor-first=Andrzej
|editor-link=Анджей Гжегорчик
|editor2-last=Rasiowa
|editor2-first=Helena
|editor2-link=Гелена Расіова
|series=Rozprawy Matematyczne
|publisher={{li|Інститут математики Польської академії наук|Institute of Mathematics of the Polish Academy of Sciences|Q=Q11713106}}
|volume=33
|page=4
}}</ref> '''ефективні числа''',{{Sfnp|van der Hoeven|2006}} '''обчислювані дійсні числа'''<ref>{{Cite journal|last=Pour-El|first=Marian Boykan|last2=Richards|first2=Ian|year=1983|title=Noncomputability in analysis and physics: a complete determination of the class of noncomputable linear operators|journal=[[Advances in Mathematics]]|volume=48|issue=1|pages=44–74|doi=10.1016/0001-8708(83)90004-X|mr=697614|doi-access=free}}</ref> або '''рекурсивні дійсні числа'''.<ref>{{Cite journal|last=Rogers|first=Hartley, Jr.|year=1959|title=The present theory of Turing machine computability|journal=Journal of the Society for Industrial and Applied Mathematics|volume=7|pages=114–130|doi=10.1137/0107009|mr=99923}}</ref> Поняття обчислюваного дійсного числа ввів 1912 року [[Еміль Борель]], скориставшись інтуїтивним поняттям обчислюваності, доступним на той час.<ref>P. Odifreddi, ''Classical Recursion Theory'' (1989), p.8. North-Holland, 0-444-87295-7</ref>

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

Число, що не обчислюється, називається '''необчислюваним''' (прикладом необчислюваного числа є {{li|константа Хайтіна|Q=Q735775}} в [[Проблема зупинки|проблемі зупинки]]).

Будь-яке [[Алгебраїчні числа|алгебричне число]] (а отже, будь-яке [[Раціональне число|раціональне]] і тим більше будь-яке [[ціле число]]) є обчислюваним. Будь-який елемент {{li|Кільце періодів|text=кільця періодів|Q=Q2835973}} (що включає [[Число пі|число π]] і багато інших [[Трансцендентне число|трансцендентних числа]]) є обчислюваним. Будь-яке обчислюване число є [[Арифметичне число|арифметичним]].

Множина всіх обчислюваних чисел є [[Зліченна множина|зліченною множиною]], а множина всіх необчислюваних чисел&nbsp;— [[Незліченна множина|незліченною]]. Множина всіх обчислюваних чисел (як і множина всіх необчислюваних чисел) [[Щільна множина|щільна]] в <math>\R</math> і в <math>\Complex.</math>

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

== Визначення ==
Дійсне число <math>x</math> називають обчислюваним<ref name="Birk">''[[Гаррет Біркгоф|Биркгоф Г.]], Барти Т.'' Современная прикладная алгебра.&nbsp;— {{М.}}, [[Мир (видавництво)|Мир]], 1976.&nbsp;— с. 375, 376.</ref>, якщо існує [[алгоритм]], який дозволяє для кожного <math>n \in P</math> обчислити за скінченне число кроків двійковий дріб <math>a = \frac{k}{2^r},\ k \in \mathbb Z,\ r \in \mathbb N</math>, такий, що <math>|x - a| < 2^{-n}</math>.

== Властивості ==

* [[Сума]], [[Віднімання|різниця]] та [[Множення|добуток]] обчислюваних чисел є обчислюваними.
* Границя [[Обчисленна функція|послідовності обчислюваних раціональних чисел]] не обов'язково є обчислюваним числом (але завжди є {{Не перекладено|Тюрінгів стрибок|тюрінговим стрибком|en|Turing jump}})
* Існує [[Бієкція|взаємно однозначна відповідність]] між обчислюваними підмножинами <math>S \subset P</math> та обчислюваними дійсними числами <math>x \in [0, 1]</math><ref name="Birk"/>.

== Див. також ==
* [[Алгоритмічна розв'язність]]
* [[Конструктивне число]]
* [[Степінь Тюрінга]]

== Примітки ==
{{reflist}}

== Література ==
{{refbegin|30em}}
* {{cite book |first1=Douglas |last1=Bridges |first2=Fred |last2=Richman |title=Varieties of Constructive Mathematics |url=https://books.google.com/books?id=oN5nsPkXhhsC |date=1987 |publisher=Cambridge University Press |isbn=978-0-521-31802-0 }}
* {{cite journal |first=Jeffry L. |last=Hirst |title=Representations of reals in reverse mathematics |journal= Bulletin of the Polish Academy of Sciences, Mathematics|year=2007 |volume=55 |issue=4 |pages=303–316  |url=https://eudml.org/doc/281227 |doi=10.4064/ba55-4-2|doi-access=free }}
* {{Cite web |title=RealLib |last=Lambov |first=Branimir |publisher=GitHub |date=5 квітня 2015 |url= https://github.com/blambov/RealLib }}
* {{cite book |author-link=Marvin Minsky |first=Marvin |last=Minsky |chapter=9. The Computable Real Numbers |title=Computation: Finite and Infinite Machines |url=https://archive.org/details/computationfinit0000mins |url-access=registration |publisher=Prentice-Hall |year=1967 |isbn=0-13-165563-9  |oclc=0131655639}}
* {{cite journal |first=Henry Gordon |last=Rice |title=Recursive real numbers |journal=Proceedings of the American Mathematical Society |year=1954 |volume=5 |issue=5 |pages=784–791 |doi=10.1090/S0002-9939-1954-0063328-5 |jstor=2031867  |doi-access=free }}
* {{cite journal |first=E. |last=Specker |author-link = Ернст Спекер|title=Nicht konstruktiv beweisbare Sätze der Analysis |journal=Journal of Symbolic Logic |year=1949 |volume=14 |issue=3 |pages=145–158  |doi=10.2307/2267043 |jstor=2267043|s2cid=11382421 |url=http://doc.rero.ch/record/304204/files/S0022481200105663.pdf |archive-url=https://web.archive.org/web/20180721231142/http://doc.rero.ch/record/304204/files/S0022481200105663.pdf |archive-date=2018-07-21 |url-status=live }}
* {{cite journal | last= Turing | first= A. M. | publication-date = 1937 | year = 1936 | title = On Computable Numbers, with an Application to the Entscheidungsproblem | periodical = Proceedings of the London Mathematical Society | series = Series 2 | volume = 42 | issue= 1 | pages = 230–65 | doi= 10.1112/plms/s2-42.1.230 | s2cid= 73712 }}<br/>{{cite journal | last = Turing | first = A. M. | publication-date = 1937 | title = On Computable Numbers, with an Application to the Entscheidungsproblem: A correction | periodical = Proceedings of the London Mathematical Society | series = Series 2 | volume = 43 | issue = 6 | pages = 544–6 | url = http://www.abelard.org/turpap2/tp2-ie.asp | doi = 10.1112/plms/s2-43.6.544 | year = 1938 }}&nbsp;— у цій праці введено обчислювані числа (і а-машини Тьюрінга); у визначенні обчислюваних чисел використано нескінченні десяткові послідовності.
* {{cite journal |last1=van der Hoeven |first1=Joris |title=Computations with effective real numbers |journal=Theoretical Computer Science |date=2006 |volume=351 |issue=1 |pages=52–60 |doi=10.1016/j.tcs.2005.09.060|doi-access=free }}
* {{cite journal |first=Oliver |last=Aberth |title=Analysis in the Computable Number Field |journal=Journal of the Association for Computing Machinery |year=1968 |volume=15 |issue=2 |pages=276–299  |doi=10.1145/321450.321460 |s2cid=18135005 |doi-access=free }} This paper describes the development of the calculus over the computable number field.
* {{cite book |first1=Errett |last1=Bishop |first2=Douglas |last2=Bridges |title=Constructive Analysis |publisher=Springer |year=1985 |isbn=0-387-15066-8 }}
* {{cite book |first1=V. |last1=Stoltenberg-Hansen |first2=J.V. |last2=Tucker |chapter=Computable Rings and Fields |editor-first=E.R. |editor-last=Griffor |title=Handbook of Computability Theory |chapter-url=https://books.google.com/books?id=KqeXZ4pPd5QC&pg=PA363 |date=1999 |publisher=Elsevier |isbn=978-0-08-053304-9 |pages=363–448}}
* {{cite book |first=Klaus |last=Weihrauch |title=Computable analysis |series=Texts in Theoretical Computer Science |publisher=Springer |year=2000 |isbn=3-540-66817-9 }}&nbsp;— у §&nbsp;1.3.2 введено визначення [[Лема про вкладені відрізки|вкладених послідовностей відрізків]], що збігаються до синглетного дійсного. Інші представлення обговорюються в §&nbsp;4.1.
* {{cite book |first=Klaus |last=Weihrauch |url=http://eccc.uni-trier.de/static/books/A_Simple_Introduction_to_Computable_Analysis_Fragments_of_a_Book/  |title=A simple introduction to computable analysis |year=1995 |publisher=Fernuniv., Fachbereich Informatik}}
{{refend}}

== Посилання ==
{{нк}}
{{Математична логіка}}
{{Quantity}}

[[Категорія:Теорія алгоритмів]]
[[Категорія:Теорія рекурсії]]