Вычислимое число: различия между версиями
| [отпатрулированная версия] | [отпатрулированная версия] |
Содержимое удалено Содержимое добавлено
Arventur (обсуждение | вклад) Определение и АИ |
Arventur (обсуждение | вклад) Нет описания правки |
||
Строка 7:
== Определение ==
Вещественное число <math>x</math> называется вычислимым, если существует [[алгоритм]], который позволяет для каждого <math>n \in P</math> вычислить за конечное число шагов двоичную дробь <math>a = \frac{k}{2^r}, k \in Z, r \in N</math>, такую, что <math>|x-a| < 2^{-n}</math><ref name="Birk">''[[Биркгоф, Гаррет|Биркгоф Г.]], Барти Т.'' Современная прикладная алгебра. - М., Мир, 1976. - с. 375,376</ref>
== Свойства ==
* [[Сумма (математика)|Сумма]], [[Вычитание|разность]] и [[Умножение|произведение]] вычислимых чисел являются вычислимыми.
* Предел [[вычислимая функция|вычислимой последовательности]] рациональных чисел не обязательно является вычислимым числом (но всегда является {{Не переведено|:en:Turing jump|Тьюринговый скачок|0′-вычислимым}})
* Существует [[биекция|взаимно однозначное соответствие]] между вычислимыми подмножествами <math>S \subset P</math> и вычислимыми вещественными числами <math>x \in [0, 1]</math><ref name="Birk"></ref>.
== См. также ==
| |||