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

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

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

Любое алгебраическое число (а значит, любое рациональное и тем более любое целое число) является вычислимым. Любой элемент кольца периодов (что включает в себя число π и многие другие трансцендентные числа) является вычислимым. Любое вычислимое число является арифметическим.

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

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

Определение

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

Свойства

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

См. также

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

Примечания

Биркгоф Г., Барти Т. Современная прикладная алгебра. — М., Мир, 1976. — с. 375, 376.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[Birk-1] Биркгоф Г., Барти Т. Современная прикладная алгебра. — М., Мир, 1976. — с. 375, 376.

Числовые системы
Счётные множества	Натуральные числа ( $\scriptstyle \mathbb {N}$ ) Целые ( $\scriptstyle \mathbb {Z}$ ) Рациональные ( $\scriptstyle \mathbb {Q}$ ) Алгебраические ( $\scriptstyle {\overline {\mathbb {Q} }}$ ) Периоды Вычислимые Арифметические
Вещественные числа и их расширения	Вещественные ( $\scriptstyle \mathbb {R}$ ) Комплексные ( $\scriptstyle \mathbb {C}$ ) Кватернионы ( $\scriptstyle \mathbb {H}$ ) Числа Кэли (октавы, октонионы) ( $\scriptstyle \mathbb {O}$ ) Седенионы ( $\scriptstyle \mathbb {S}$ ) Альтернионы Дуальные Гиперкомплексные Супердействительные Гипервещественные Сюрреальные
Инструменты расширения числовых систем	Процедура Кэли — Диксона Теорема Фробениуса Теорема Гурвица
Другие числовые системы	Кардинальные числа Порядковые числа (трансфинитные, ординалы) p-адические Супернатуральные числа Интервальные числа
См. также	Двойные числа Иррациональные числа Трансцендентные числа Числовой луч Бикватернион