Вычислимое число
В статье не хватает ссылок на источники (см. также рекомендации по поиску). |
В математике вычислимое (или рекурсивное) число — это число, которое может быть вычислено с любой заданной точностью с помощью алгоритма (для комплексных чисел должны быть вычислимы и действительная, и мнимая части).
Число, не являющееся вычислимым, называется невычислимым (примером невычислимого числа является константа Хайтина в проблеме остановки).
Любое алгебраическое число (а значит, любое рациональное и тем более любое целое число) является вычислимым. Любой элемент кольца периодов (что включает в себя число π и многие другие трансцендентные числа) является вычислимым. Любое вычислимое число является арифметическим.
Множество всех вычислимых чисел является счётным множеством, а множество всех невычислимых чисел — несчётным. Множество всех вычислимых чисел (равно как и множество всех невычислимых чисел) плотно в [math]\displaystyle{ \R }[/math] и в [math]\displaystyle{ \Complex. }[/math]
Порядок на множестве вычислимых действительных чисел изоморфен порядку на множестве рациональных чисел.
Определение
Вещественное число [math]\displaystyle{ x }[/math] называется вычислимым[1], если существует алгоритм, который позволяет для каждого [math]\displaystyle{ n \in P }[/math] вычислить за конечное число шагов двоичную дробь [math]\displaystyle{ a = \frac{k}{2^r},\ k \in \mathbb Z,\ r \in \mathbb N }[/math], такую, что [math]\displaystyle{ |x - a| \lt 2^{-n} }[/math].
Свойства
- Сумма, разность и произведение вычислимых чисел являются вычислимыми.
- Предел вычислимой последовательности рациональных чисел не обязательно является вычислимым числом (но всегда является 0′-вычислимым )
- Существует взаимно однозначное соответствие между вычислимыми подмножествами [math]\displaystyle{ S \subset P }[/math] и вычислимыми вещественными числами [math]\displaystyle{ x \in [0, 1] }[/math][1].
См. также
Примечания
- ↑ 1,0 1,1 Биркгоф Г., Барти Т. Современная прикладная алгебра. — М., Мир, 1976. — с. 375, 376.