Изменения

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

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

8 байт убрано, 01:56, 14 января 2013
м
Нет описания правки
<tex>\Rightarrow</tex>:
Так как По определению <tex> \alpha </tex>, множество <tex> A = \{ a \in \mathbb Q \mid a < \alpha \} </tex> перечислимо. Кроме того, то можно перечислить его элементы в возрастающем порядке<tex> \sup A = \alpha </tex>. По определению нижней грани, они и дают нам необходимую последовательность, так как ее пределом будет <tex> \lim forall \varepsilon > 0\limits_{n \to exists x_\infty} a_n = varepsilon \sup in A : \varepsilon > \alpha - x_\varepsilon </tex>. Тогда можно взять, например, последовательность <tex> a_n = x_{\alpha frac 1 n} </tex>.
<tex>\Leftarrow</tex>:
Обозначим множества <tex> \{a \in \mathbb Q \mid a < \alpha \} </tex> и <tex> \{a \in \mathbb Q \mid a > \alpha \} </tex> за <tex> A </tex> и <tex> B </tex> соответственно.
Если <tex> \alpha </tex> рационально, то необходимые (полу)разрешатели разрешители строятся тривиально.
В противном случае, так как <tex> B = \mathbb Q \setminus A</tex>, то перечислимость множеств <tex> A </tex> и <tex> B </tex> равносильна разрешимости множества <tex> A </tex>, которая, в свою очередь, равносильна вычислимости <tex> \alpha </tex>.
== Последовательность Шпеккера ==
ОчевидноМножество всех программ счетно, поэтому множество вычислимых чисел также счетно, так как его мощность можно ограничить сверху мощностью не более чем счетной степени множества <tex> \mathbb 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> невычислимо.
}}
== Ссылки ==
* ''Верещагин Н. К., Шень А.'' Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции — М.: МЦНМО, 1999 - С. 14
* [http://en.wikipedia.org/wiki/Computable_number| Computable number]* [http://en.wikipedia.org/wiki/Specker_sequence| Specker sequence]
[[Категория: Теория вычислимости]]
[[Категория: Теория формальных языков]]
689
правок

Навигация