Изменения

Перейти к: навигация, поиск

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

1375 байт добавлено, 21:49, 12 января 2013
Последовательность Шпеккера
== Последовательность Шпеккера ==
 
Очевидно, множество вычислимых чисел счетно, так как его мощность можно ограничить сверху мощностью не более чем счетной степени множества <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> невычислимо.
}}
689
правок

Навигация