Меню Главная Случайная статья Настройки Вычислимое число Материал из https://ru.wikipedia.org В математике вычислимое (или рекурсивное) число — это число, которое может быть вычислено с любой заданной точностью с помощью алгоритма (для комплексных чисел должны быть вычислимы и действительная, и мнимая части). Число, не являющееся вычислимым, называется невычислимым (примером невычислимого числа является константа Хайтина в проблеме остановки). Любое алгебраическое число (а значит, любое рациональное и тем более любое целое число) является вычислимым. Любой элемент кольца периодов (что включает в себя число и многие другие трансцендентные числа) является вычислимым. Любое вычислимое число является арифметическим. Множество всех вычислимых чисел является счётным множеством, а множество всех невычислимых чисел — несчётным. Множество всех вычислимых чисел (равно как и множество всех невычислимых чисел) плотно в ${\displaystyle \mathbb {R} }$ и в ${\displaystyle \mathbb {C} .}$ Порядок на множестве вычислимых действительных чисел изоморфен порядку на множестве рациональных чисел. Содержание 1 Определение 2 Свойства 3 См. также 4 Примечания Определение Вещественное число ${\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]. См. также Алгоритмическая разрешимость Степень неразрешимости[англ.] Примечания 1 2 Биркгоф Г., Барти Т. Современная прикладная алгебра. — М., Мир, 1976. — с. 375, 376.