Русская Википедия:Вычислимое число

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

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

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

Множество всех вычислимых чисел является счётным множеством, а множество всех невычислимых чисел — несчётным. Множество всех вычислимых чисел (равно как и множество всех невычислимых чисел) плотно в <math>\R</math> и в <math>\Complex.</math>

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

Определение

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

Свойства

• Сумма, разность и произведение вычислимых чисел являются вычислимыми.
• Предел вычислимой последовательности рациональных чисел не обязательно является вычислимым числом (но всегда является Шаблон:Нп1)
• Существует взаимно однозначное соответствие между вычислимыми подмножествами <math>S \subset P</math> и вычислимыми вещественными числами <math>x \in [0, 1]</math>.

См. также

• Алгоритмическая разрешимость
• Шаблон:Нп1