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

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

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

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

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

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

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

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

Визначення

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

Властивості

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

Див. також

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