689
правок
Изменения
→Последовательность Шпеккера
== Последовательность Шпеккера ==
Очевидно, множество вычислимых чисел счетно, так как его мощность можно ограничить сверху мощностью не более чем счетной степени множества <tex> \mathbb Q </tex>. Однако, множество вещественных чисел несчетно, значит, существуют невычислимые вещественные числа. Построим явно пример такого числа.
{{Определение
|statement=
Число <tex> q = \lim\limits_{n \to \infty} q_n </tex> перечислимо снизу, но невычислимо.
|proof=
<tex> q </tex> перечислимо снизу, как предел возрастающей вычислимой последовательности рациональных чисел.
Допустим теперь, что <tex> q </tex> вычислимо.
Пусть <tex> A = \{p \mid p(p) = 1\}</tex>. Рассмотрим двоичную запись числа <tex> q </tex>, если ее <tex> n </tex>-ный знак после запятой равен 1, то <tex> n \in A </tex>, иначе {{---}} <tex> n \notin A </tex>. Мы построили разрешатель для множества <tex> A </tex>. Тем не менее, мы знаем, что <tex> A </tex> {{---}} неразрешимое множество, и это невозможно, значит, <tex> q </tex> невычислимо.
}}
