WikiSort.ru - Не сортированное

В этой статье не хватает ссылок на источники информации. Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена. Вы можете отредактировать эту статью, добавив ссылки на авторитетные источники. Эта отметка установлена 25 августа 2012 года.

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

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

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

Определение

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

Свойства

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

См. также

• Степень неразрешимости (англ.)

Примечания

Это заготовка статьи по математике. Вы можете помочь проекту, дополнив её.