Редактирование: Вычислимые числа
Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 4: | Строка 4: | ||
{{Определение | {{Определение | ||
|definition= | |definition= | ||
− | Действительное число <tex> \alpha </tex> называется '''вычислимым''' ( | + | Действительное число <tex> \alpha </tex> называется '''вычислимым''' (computable number), если существует вычислимая функция <tex> a: \mathbb Q \rightarrow \mathbb Q </tex>, такая, что <tex>|\alpha - a(\varepsilon)| < \varepsilon </tex> для любого рационального <tex> \varepsilon > 0 </tex>. |
}} | }} | ||
Строка 11: | Строка 11: | ||
{{Теорема | {{Теорема | ||
|statement= | |statement= | ||
− | Число <tex> \alpha </tex> вычислимо | + | Число <tex> \alpha </tex> вычислимо тогда и только тогда, когда множество <tex>A = \{x \in Q \mid x < \alpha \} </tex> разрешимо. |
|proof= | |proof= | ||
− | <tex> \Longrightarrow </tex> | + | <tex> \Longrightarrow </tex>: |
− | + | Если <tex> \alpha </tex> {{---}} рациональное, то существует тривиальный разрешитель для <tex> A </tex>, который просто сравнивает полученный элемент с <tex> \alpha </tex>. | |
− | + | В противном случае, построим разрешитель для <tex> A </tex>: | |
− | + | <tex>p(x)</tex>: | |
− | '''for''' <tex> n = 1 | + | '''for''' <tex> n = 1.. \infty </tex>: |
− | '''if''' <tex> x < a | + | '''if''' <tex> x < a(\frac1n) - \frac1n </tex>: |
− | '''return''' | + | '''return''' 1 |
− | '''if''' <tex> x > a | + | '''if''' <tex> x > a(\frac1n) + \frac1n </tex>: |
− | '''return''' | + | '''return''' 0 |
− | <tex> \Longleftarrow </tex> | + | <tex> \Longleftarrow </tex>: |
− | + | Построим функцию <tex> a(\varepsilon) </tex>: | |
− | + | <tex> a(\varepsilon) </tex>: | |
− | '''for''' <tex> x \in A </tex> | + | '''for''' <tex> x \in A </tex>: |
− | '''if''' <tex> x + \varepsilon \notin A </tex> | + | '''if''' <tex> x + \varepsilon \notin A </tex>: |
− | '''return''' | + | '''return''' x |
− | + | Так как <tex> A </tex> разрешимо, <tex> \alpha = \sup A </tex> и для любого <tex> x \in A </tex> проверка в условном операторе завершается за конечное время, то функция <tex> a(\varepsilon) </tex> вычислима для любого рационального <tex> \varepsilon </tex>. | |
}} | }} | ||
Строка 44: | Строка 44: | ||
{{Теорема | {{Теорема | ||
|statement= | |statement= | ||
− | Число <tex> \alpha </tex> вычислимо | + | Число <tex> \alpha </tex> вычислимо тогда и только тогда, когда последовательность знаков представляющей его двоичной записи вычислима. |
|proof= | |proof= | ||
− | <tex> \Longrightarrow </tex> | + | <tex> \Longrightarrow </tex>: |
− | + | Если число <tex> \alpha </tex> {{---}} рациональное, то необходимую последовательность можно получить, воспользовавшись стандартным алгоритмом перевода числа в двоичную систему счисления. Рассмотрим случай, когда <tex> \alpha \in \mathbb R \setminus \mathbb Q </tex>. | |
− | + | Очевидно, двоичная запись целой части <tex> \alpha </tex> всегда вычислима (так как множество чисел, меньших <tex> \alpha </tex>, разрешимо, то можно перебрать все целые числа в порядке возрастания их абсолютных величин и найти наибольшее число, меньшее <tex> \alpha </tex>), поэтому будем считать, что <tex> \alpha \in (0; 1) </tex>. | |
− | + | Напишем программу, которая по числу <tex> n </tex> вычисляет <tex> n </tex>-ный знак числа <tex> \alpha </tex> после запятой: | |
− | + | <tex>p(n)</tex>: | |
− | + | l = 0, r = 1 | |
− | '''for''' <tex> k = 1 | + | '''for''' <tex> k = 1..n </tex>: |
− | <tex> m = \ | + | <tex> m = \frac{l+r}2 </tex> |
− | '''if''' <tex> m < \alpha</tex> | + | '''if''' <tex> m < \alpha</tex>: |
− | + | l = m, t = 1 | |
− | '''else''' | + | '''else''': |
− | + | r = m, t = 0 | |
− | '''return''' | + | '''return''' t |
− | <tex> \Longleftarrow </tex> | + | <tex> \Longleftarrow </tex>: |
− | + | Для любого рационального <tex> \varepsilon > 0 </tex>, найдем <tex> n: 2^{-n} < \varepsilon </tex>, тогда в качестве значения функции <tex> a(\varepsilon) </tex> можно взять часть последовательности знаков двоичной записи <tex> \alpha </tex> с <tex> n </tex> знаками после запятой. | |
}} | }} | ||
{{Определение | {{Определение | ||
|definition= | |definition= | ||
− | Последовательность рациональных чисел <tex> \{ r_n \} </tex> '''вычислимо сходится''' к <tex> \alpha </tex>, если существует вычислимая функция <tex> N: \mathbb Q \rightarrow \mathbb N </tex>, такая, что для любого рационального <tex> \varepsilon > 0 </tex> выполняется <tex>\forall n > | + | Последовательность рациональных чисел <tex> \{ r_n \} </tex> '''вычислимо сходится''' к <tex> \alpha </tex>, если существует вычислимая функция <tex> N: \mathbb Q \rightarrow \mathbb N </tex>, такая, что для любого рационального <tex> \varepsilon > 0 </tex> выполняется <tex>\forall n > N(\varepsilon): |r_n - \alpha| < \varepsilon </tex>. |
}} | }} | ||
{{Теорема | {{Теорема | ||
|statement= | |statement= | ||
− | Число <tex> \alpha </tex> вычислимо | + | Число <tex> \alpha </tex> вычислимо тогда и только тогда, когда существует вычислимая последовательность рациональных чисел, вычислимо сходящаяся к <tex> \alpha </tex>. |
|proof= | |proof= | ||
− | <tex> \Longrightarrow </tex> | + | <tex> \Longrightarrow </tex>: |
− | + | Так как <tex> \alpha </tex> вычислимо, то, согласно предыдущей теореме, вычислима и его двоичная запись. Пусть <tex> r_n </tex> {{---}} часть последовательности знаков двоичной записи <tex> \alpha </tex> с <tex> n </tex> знаками после запятой. Данная последовательность вычислима, а также вычислимо сходится к <tex> \alpha </tex>, так как <tex> N(\varepsilon) = \lceil -\log_2 \varepsilon \rceil</tex>. | |
− | <tex> \Longleftarrow </tex> | + | <tex> \Longleftarrow </tex>: |
− | + | Пусть <tex> a(\varepsilon) = r_{N(\varepsilon)} </tex>, тогда <tex> \alpha </tex> вычислимо по определению. | |
}} | }} | ||
Строка 89: | Строка 89: | ||
|statement= | |statement= | ||
− | Пусть числа <tex> \alpha, \beta </tex> вычислимы. Тогда также вычислимы числа <tex> \alpha + \beta </tex>, <tex> \alpha - \beta </tex>, <tex> \alpha \beta </tex> и <tex> \ | + | Пусть числа <tex> \alpha, \beta </tex> вычислимы. Тогда также вычислимы числа <tex> \alpha + \beta </tex>, <tex> \alpha - \beta </tex>, <tex> \alpha \beta </tex> и <tex> \frac \alpha \beta </tex>. |
|proof= | |proof= | ||
В пределах этого доказательства будем обозначать функцию-приближение для произвольного вычислимого числа <tex> x </tex> как <tex> f_x </tex>. | В пределах этого доказательства будем обозначать функцию-приближение для произвольного вычислимого числа <tex> x </tex> как <tex> f_x </tex>. | ||
Строка 95: | Строка 95: | ||
Для того, чтобы получить приближение для результата операции, нам нужно выразить функцию-результат через приближения для операндов. | Для того, чтобы получить приближение для результата операции, нам нужно выразить функцию-результат через приближения для операндов. | ||
− | Заметим, что <tex> |(\alpha \pm \beta) - (a \pm b)| \ | + | Заметим, что <tex> |(\alpha \pm \beta) - (a \pm b)| \le |\alpha - a| \pm |\beta - b| </tex>, для произвольных рациональных <tex> a, b </tex>, значит, в качестве необходимых функций для <tex> \alpha + \beta </tex> и <tex> \alpha - \beta </tex> можно взять |
− | <tex > f_{\alpha + \beta}(\varepsilon) = f_{\alpha} | + | <tex> f_{\alpha + \beta}(\varepsilon) = f_{\alpha}(\frac \varepsilon 2) + f_{\beta}(\frac \varepsilon 2) </tex> |
и | и | ||
− | <tex> f_{\alpha - \beta}(\varepsilon) = f_{\alpha} | + | <tex> f_{\alpha - \beta}(\varepsilon) = f_{\alpha}(\frac \varepsilon 2) - f_{\beta}(\frac \varepsilon 2) </tex> |
− | соответственно (при подстановке в неравенство <tex> f_{\alpha} </tex> и <tex> f_{\beta} </tex> вместо <tex> a </tex> и <tex> b </tex> каждый модуль в правой части не превосходит <tex> \ | + | соответственно (при подстановке в неравенство <tex> f_{\alpha} </tex> и <tex> f_{\beta} </tex> вместо <tex> a </tex> и <tex> b </tex> каждый модуль в правой части не превосходит <tex> \frac \varepsilon 2 </tex>, поэтому, <tex> f_{\alpha \pm \beta} </tex> не превосходит <tex> \varepsilon </tex>). |
Далее, так как | Далее, так как | ||
− | <tex> |\alpha \beta - ab| = |(\alpha \beta - a \beta) + (a \beta - ab)| \ | + | <tex> |\alpha \beta - ab| = |(\alpha \beta - a \beta) + (a \beta - ab)| \le |\beta||\alpha - a| + |a||\beta - b| \le |b_\beta||\alpha - a| + |a||\beta - b|</tex>, |
− | где | + | где <tex> b_\beta \in \mathbb Q, |b_\beta| > |\beta| </tex> (<tex> b_\beta </tex>, очевидно, можно найти за конечное время), то |
− | <tex> f_{\alpha \beta}(\varepsilon) = f_{\alpha} | + | <tex> f_{\alpha \beta}(\varepsilon) = f_{\alpha}(\frac \varepsilon {b_\beta}) f_{\beta}(\frac \varepsilon a) </tex>. |
− | Убедимся в вычислимости числа <tex> \ | + | Убедимся в вычислимости числа <tex> \frac 1 \alpha </tex>: |
− | <tex> | + | <tex> |\frac 1 \alpha - \frac1a| \le \frac {|a - \alpha|}{a a_\alpha} </tex>, где <tex> a_\alpha \in \mathbb Q, |a_\alpha| < |\alpha| </tex>. |
− | <tex> f_{\frac | + | <tex> f_{\frac 1 \alpha}(\varepsilon) = f_{\alpha}(\varepsilon a a_\alpha) </tex>. |
− | Отсюда, <tex> \ | + | Отсюда, <tex> \frac \alpha \beta = \frac1 \alpha \beta </tex> также вычислимо. |
}} | }} | ||
Строка 135: | Строка 135: | ||
Заметим, что для вычислимого <tex> t </tex> значение <tex> P(t) </tex> также вычислимо, так как в процессе его вычисления используются только операции, вычислимость значений которых уже была ранее доказана. | Заметим, что для вычислимого <tex> t </tex> значение <tex> P(t) </tex> также вычислимо, так как в процессе его вычисления используются только операции, вычислимость значений которых уже была ранее доказана. | ||
− | Теперь, если полином имеет разные знаки на отрезках <tex> [a; x] </tex> и <tex> [x; b] </tex>, то для поиска <tex> x </tex> можно воспользоваться двоичным поиском | + | Теперь, если полином имеет разные знаки на отрезках <tex> [a; x] </tex> и <tex> [x; b] </tex>, то для поиска <tex> x </tex> можно воспользоваться двоичным поиском для поиска нуля на <tex> [a; b] </tex>, иначе {{---}} троичным поиском для поиска минимума или максимума на <tex> [a; b] </tex>. |
Останавливая тот или иной алгоритм, когда текущая длина интервала становится меньше <tex> \varepsilon </tex> и возвращая левую границу в качестве ответа, получаем функцию <tex> a_x(\varepsilon) </tex>. | Останавливая тот или иной алгоритм, когда текущая длина интервала становится меньше <tex> \varepsilon </tex> и возвращая левую границу в качестве ответа, получаем функцию <tex> a_x(\varepsilon) </tex>. | ||
Строка 142: | Строка 142: | ||
{{Теорема | {{Теорема | ||
|statement= | |statement= | ||
− | Предел вычислимо сходящейся вычислимой последовательности | + | Предел вычислимо сходящейся вычислимой последовательности вычислимых чисел вычислим. |
|proof= | |proof= | ||
− | Пусть <tex> \alpha = \lim\limits_{n \to \infty} r_n </tex>. Запишем формально данные нам условия: | + | Пусть рассматриваемая последовательность {{---}} <tex> r_n </tex>, и <tex> \alpha = \lim\limits_{n \to \infty} r_n </tex>. Запишем формально данные нам условия: |
− | <tex> \forall \varepsilon_1 > 0\ \forall n > (\varepsilon_1): |r(n) - \alpha| < \varepsilon_1 </tex> | + | <tex> \forall \varepsilon_1 > 0\ \forall n > N(\varepsilon_1): |r(n) - \alpha| < \varepsilon_1 </tex> |
<tex> \forall n\ \forall \varepsilon_2 > 0\ |r(n) - p_n(\varepsilon_2)| < \varepsilon_2 </tex> | <tex> \forall n\ \forall \varepsilon_2 > 0\ |r(n) - p_n(\varepsilon_2)| < \varepsilon_2 </tex> | ||
Строка 154: | Строка 154: | ||
Построим функцию <tex> a(\varepsilon) </tex>, которая дает приближение к <tex> \alpha </tex> с точностью до <tex> \varepsilon </tex>: | Построим функцию <tex> a(\varepsilon) </tex>, которая дает приближение к <tex> \alpha </tex> с точностью до <tex> \varepsilon </tex>: | ||
− | + | <tex> a(\varepsilon) </tex>: | |
− | n = <tex> N | + | n = <tex> N(\frac \varepsilon 2) + 1 </tex> |
− | '''return''' <tex> p_n | + | '''return''' <tex> p_n(\frac \varepsilon 2) </tex> |
− | Так как <tex> | + | Так как <tex> |\alpha - p_n(\frac \varepsilon 2)| < |\alpha - r(n)| + |r(n) - p_n(\frac \varepsilon 2)| </tex>, первое слагаемое меньше <tex> \frac \varepsilon 2 </tex> по выбору <tex> n </tex>, второе {{---}} в силу вычислимости <tex> p_n </tex>, то <tex> |\alpha - p_n(\frac \varepsilon 2)| < \varepsilon </tex>, и <tex> a(\varepsilon) </tex> действительно вычисляет требуемое приближение. |
}} | }} | ||
Строка 165: | Строка 165: | ||
{{Определение | {{Определение | ||
|definition= | |definition= | ||
− | Действительное число <tex> \alpha </tex> называется '''перечислимым снизу''' ( | + | Действительное число <tex> \alpha </tex> называется '''перечислимым снизу''' (recursively enumerable number), если множество <tex> \{ a \in \mathbb Q \mid a < \alpha \} </tex> перечислимо. |
}} | }} | ||
Строка 177: | Строка 177: | ||
{{Теорема | {{Теорема | ||
|statement= | |statement= | ||
− | Число <tex> \alpha </tex> перечислимо снизу | + | Число <tex> \alpha </tex> перечислимо снизу тогда и только тогда, когда существует вычислимая возрастающая последовательность рациональных чисел, пределом которой является <tex> \alpha </tex>. |
|proof= | |proof= | ||
− | <tex>\ | + | <tex>\Rightarrow</tex>: |
− | + | Так как <tex> A = \{ a \in \mathbb Q \mid a < \alpha \} </tex> перечислимо, то можно перечислить его элементы в возрастающем порядке, они и дают нам необходимую последовательность, так как ее пределом будет <tex> \lim \limits_{n \to \infty} a_n = \sup A = \alpha </tex>. | |
− | + | <tex>\Leftarrow</tex>: | |
− | <tex> | + | Построим полуразрешитель для множества <tex> A </tex>: |
− | : | + | p(x): |
+ | '''for''' n in <tex>1..\infty</tex>: | ||
+ | '''if''' <tex> x < a_n </tex>: | ||
+ | '''return''' 1 | ||
− | + | Если <tex> x \in A</tex>, то <tex> \alpha - x = t > 0 </tex>, и так как <tex> \exists N:\ \forall n > N |a_n - \alpha| < t </tex>, то программа вернет ответ при <tex> n > N </tex>. | |
− | |||
− | |||
− | |||
− | |||
− | |||
}} | }} | ||
{{Теорема | {{Теорема | ||
|statement= | |statement= | ||
− | Число <tex> \alpha </tex> вычислимо | + | Число <tex> \alpha </tex> вычислимо тогда и только тогда, когда оно перечислимо сверху и снизу. |
|proof= | |proof= | ||
Обозначим множества <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> \{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> \alpha </tex> рационально, то необходимые (полу)разрешатели строятся тривиально. |
В противном случае, так как <tex> B = \mathbb Q \setminus A</tex>, то перечислимость множеств <tex> A </tex> и <tex> B </tex> равносильна разрешимости множества <tex> A </tex>, которая, в свою очередь, равносильна вычислимости <tex> \alpha </tex>. | В противном случае, так как <tex> B = \mathbb Q \setminus A</tex>, то перечислимость множеств <tex> A </tex> и <tex> B </tex> равносильна разрешимости множества <tex> A </tex>, которая, в свою очередь, равносильна вычислимости <tex> \alpha </tex>. | ||
Строка 210: | Строка 208: | ||
== Последовательность Шпеккера == | == Последовательность Шпеккера == | ||
− | + | Очевидно, множество вычислимых чисел счетно, так как его мощность можно ограничить сверху мощностью не более чем счетной степени множества <tex> \mathbb Q </tex>. Однако, множество вещественных чисел несчетно, значит, существуют невычислимые вещественные числа. Построим явно пример такого числа. | |
{{Определение | {{Определение | ||
|definition= | |definition= | ||
− | Пусть <tex> A </tex> {{---}} некоторое перечислимое, но неразрешимое множество натуральных чисел. | + | Пусть <tex> A </tex> {{---}} некоторое перечислимое, но неразрешимое множество натуральных чисел. Занумеруем его элементы. '''Последовательностью Шпеккера''' <tex> \{q_n\} </tex> называется последовательность рациональных чисел, <tex>n</tex>-ный член которой определяется как <tex> q_n = \sum\limits_{k=1}^{n} 2^{-A(n)-1} </tex>. |
}} | }} | ||
− | Данная последовательность строго возрастает и ограничена числом <tex> 1 </tex>, следовательно, | + | Данная последовательность строго возрастает и ограничена числом <tex> 1 </tex>, следовательно, по признаку Вейерштрасса, она сходится. |
{{Теорема | {{Теорема | ||
Строка 225: | Строка 223: | ||
<tex> q </tex> перечислимо снизу, как предел возрастающей вычислимой последовательности рациональных чисел. | <tex> q </tex> перечислимо снизу, как предел возрастающей вычислимой последовательности рациональных чисел. | ||
− | Допустим теперь, что <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 = \{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 | |
− | + | * http://en.wikipedia.org/wiki/Specker_sequence | |
− | |||
− | * ''Верещагин Н. К., Шень А.'' | ||
− | * | ||
− | * | ||
+ | [[Категория: Теория вычислимости]] | ||
[[Категория: Теория формальных языков]] | [[Категория: Теория формальных языков]] | ||
− | |||
− |