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

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

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

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

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

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

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

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

Визначення

Дійсне число $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]$.

Див. також

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

Література

• Шаблон:Cite book
• Шаблон:Cite journal
• Шаблон:Cite web
• Шаблон:Cite book
• Шаблон:Cite journal
• Шаблон:Cite journal
• Шаблон:Cite journal
  Шаблон:Cite journal — у цій праці введено обчислювані числа (і а-машини Тьюрінга); у визначенні обчислюваних чисел використано нескінченні десяткові послідовності.
• Шаблон:Cite journal
• Шаблон:Cite journal This paper describes the development of the calculus over the computable number field.
• Шаблон:Cite book
• Шаблон:Cite book
• Шаблон:Cite book — у § 1.3.2 введено визначення вкладених послідовностей відрізків, що збігаються до синглетного дійсного. Інші представлення обговорюються в § 4.1.
• Шаблон:Cite book