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

Вони також відомі як рекурсивні числа, ефективні числа, обчислювані дійсні числа або рекурсивні дійсні числа. Поняття обчислюваного дійсного числа ввів 1912 року Еміль Борель, скориставшись інтуїтивним поняттям обчислюваності, доступним на той час.P. Odifreddi, Classical Recursion Theory (1989), p.8. North-Holland, 0-444-87295-7

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

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

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

Множина всіх обчислюваних чисел є зліченною множиною, а множина всіх необчислюваних чисел — незліченною. Множина всіх обчислюваних чисел (як і множина всіх необчислюваних чисел) щільна в і в

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

Визначення Дійсне число називають обчислюванимБиркгоф Г., Барти Т. Современная прикладная алгебра. — , Мир, 1976. — с. 375, 376., якщо існує алгоритм, який дозволяє для кожного обчислити за скінченне число кроків двійковий дріб , такий, що .

Властивості

Сума, різниця та добуток обчислюваних чисел є обчислюваними. Границя послідовності обчислюваних раціональних чисел не обов'язково є обчислюваним числом (але завжди є ) Існує взаємно однозначна відповідність між обчислюваними підмножинами та обчислюваними дійсними числами .

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

Примітки

Література

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

This paper describes the development of the calculus over the computable number field.

 — у § 1.3.2 введено визначення вкладених послідовностей відрізків, що збігаються до синглетного дійсного. Інші представлення обговорюються в § 4.1.

Посилання