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

Материал из Википедии — свободной энциклопедии
(перенаправлено с «Вычислимые числа»)
Перейти к навигации Перейти к поиску

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

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

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

Множество всех вычислимых чисел является счётным множеством, а множество всех невычислимых чисел — несчётным. Множество всех вычислимых чисел (равно как и множество всех невычислимых чисел) плотно в и в

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

Определение

[править | править код]

Вещественное число называется вычислимым[1], если существует алгоритм, который позволяет для каждого вычислить за конечное число шагов двоичную дробь , такую, что .

Примечания

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