Вычислимое число

В статье не хватает ссылок на источники (см. рекомендации по поиску). Информация должна быть проверяема, иначе она может быть удалена. Вы можете отредактировать статью, добавив ссылки на авторитетные источники в виде сносок. (25 августа 2012)

В математике вычислимое (или рекурсивное) число — это число, которое может быть вычислено с любой заданной точностью с помощью алгоритма (для комплексных чисел должны быть вычислимы и действительная, и мнимая части).

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

Любое

Множество всех вычислимых чисел является счётным множеством, а множество всех невычислимых чисел — несчётным. Множество всех вычислимых чисел (равно как и множество всех невычислимых чисел) плотно в ${\displaystyle \mathbb {R} }$ и в ${\displaystyle \mathbb {C} .}$

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

• Сумма, разность и произведение вычислимых чисел являются вычислимыми.
• Предел вычислимой последовательности рациональных чисел не обязательно является вычислимым числом (но всегда является 0′-вычислимым^[англ.])
• Существует взаимно однозначное соответствие между вычислимыми подмножествами ${\displaystyle S\subset P}$ и вычислимыми вещественными числами ${\displaystyle x\in [0,1]}$^[1].

• Алгоритмическая разрешимость
• Степень неразрешимости^[англ.]

Это заготовка статьи по математике. Помогите Википедии, дополнив её.