Вычислимые числа — различия между версиями
Sementry (обсуждение | вклад) м |
м (rollbackEdits.php mass rollback) |
||
(не показана 31 промежуточная версия 5 участников) | |||
Строка 4: | Строка 4: | ||
{{Определение | {{Определение | ||
|definition= | |definition= | ||
− | Действительное число <tex> \alpha </tex> называется '''вычислимым''' (computable number), если существует вычислимая функция <tex> a: \mathbb Q \rightarrow \mathbb Q </tex>, такая, что <tex>|\alpha - a(\varepsilon)| < \varepsilon </tex> для любого рационального <tex> \varepsilon > 0 </tex>. | + | Действительное число <tex> \alpha </tex> называется '''вычислимым''' (англ. ''computable number''), если существует [[Вычислимые функции|вычислимая функция]] <tex> a(\varepsilon): \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>\iff</tex> множество <tex>A = \{x \in \mathbb Q \mid x < \alpha \} </tex> [[Разрешимые (рекурсивные) языки|разрешимо]]. |
|proof= | |proof= | ||
− | <tex> \Longrightarrow </tex> | + | <tex> \Longrightarrow </tex> |
− | Если <tex> \alpha </tex> {{---}} рациональное, то существует тривиальный разрешитель для <tex> A </tex>, который просто сравнивает полученный элемент с <tex> \alpha </tex>. | + | : Если <tex> \alpha </tex> {{---}} рациональное, то существует тривиальный разрешитель для <tex> A </tex>, который просто сравнивает полученный элемент с <tex> \alpha </tex>. |
− | В противном случае, построим разрешитель для <tex> A </tex>: | + | : В противном случае, построим разрешитель для <tex> A </tex>: |
− | <tex>p(x)</tex>: | + | '''function''' <tex> p(x)</tex>: |
− | '''for''' <tex> n = 1 | + | '''for''' <tex> n = 1</tex> '''to''' <tex>\infty </tex> |
− | '''if''' <tex> x < a(\ | + | '''if''' <tex> x < a \left(\dfrac{1}{n} \right) - \dfrac{1}{n} </tex> |
− | '''return''' 1 | + | '''return''' <tex>1</tex> |
− | '''if''' <tex> x > a(\ | + | '''if''' <tex> x > a \left(\dfrac{1}{n} \right) + \dfrac{1}{n} </tex> |
− | '''return''' 0 | + | '''return''' <tex>0</tex> |
− | <tex> \Longleftarrow </tex> | + | <tex> \Longleftarrow </tex> |
− | Построим функцию <tex> a(\varepsilon) </tex> | + | : Построим функцию <tex> a(\varepsilon) </tex> |
− | <tex> a(\varepsilon) </tex>: | + | '''function''' <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''' x | + | '''return''' <tex>x</tex> |
− | Так как <tex> A </tex> разрешимо, <tex> \alpha = \sup A </tex> и для любого <tex> x \in A </tex> проверка в условном операторе завершается за конечное время, то функция <tex> a(\varepsilon) </tex> вычислима для любого рационального <tex> \varepsilon </tex>. | + | : Так как <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> вычислимо <tex>\iff</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 \in \mathbb R \setminus \mathbb Q </tex>. |
− | Очевидно, двоичная запись целой части <tex> \alpha </tex> всегда вычислима (так как множество чисел, меньших <tex> \alpha </tex>, разрешимо, то можно перебрать все целые числа в порядке возрастания их абсолютных величин и найти наибольшее число, меньшее <tex> \alpha </tex>), поэтому будем считать, что <tex> \alpha \in (0; 1) </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> n </tex> вычисляет <tex> n </tex>-ный знак после запятой в двоичном представлении числа <tex> \alpha </tex> : |
− | <tex>p(n)</tex>: | + | '''function''' <tex>p(n)</tex>: |
− | l = 0, r = 1 | + | <tex>l = 0, r = 1 </tex> |
− | '''for''' <tex> k = 1 | + | '''for''' <tex> k = 1</tex> '''to''' <tex>n </tex> |
− | <tex> m = \ | + | <tex> m = \dfrac{l+r}{2} </tex> |
− | '''if''' <tex> m < \alpha</tex> | + | '''if''' <tex> m < \alpha</tex> |
− | l = m, t = 1 | + | <tex>l = m, t = 1</tex> |
− | '''else''' | + | '''else''' |
− | r = m, t = 0 | + | <tex>r = m, t = 0</tex> |
− | '''return''' t | + | '''return''' <tex>t</tex> |
− | <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> знаками после запятой. | + | : Для любого рационального <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 > N(\varepsilon): |r_n - \alpha| < \varepsilon </tex>. | + | Последовательность рациональных чисел <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>\iff</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> \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> вычислимо по определению. | + | : Пусть <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> \dfrac {\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)| \leqslant |\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}\left(\dfrac {\varepsilon} {2}\right) + f_{\beta}\left(\dfrac {\varepsilon} {2}\right) </tex> |
и | и | ||
− | <tex> f_{\alpha - \beta}(\varepsilon) = f_{\alpha}(\ | + | <tex> f_{\alpha - \beta}(\varepsilon) = f_{\alpha}\left(\dfrac {\varepsilon} {2}\right) - f_{\beta}\left(\dfrac {\varepsilon} {2}\right) </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> \dfrac {\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)| \leqslant |\beta||\alpha - a| + |a||\beta - b| \leqslant |b_\beta||\alpha - a| + |a||\beta - b|</tex>, |
− | где <tex> b_\beta \in \mathbb Q, |b_\beta| > |\beta| </tex> | + | где <tex>b_\beta</tex> {{---}} наименьшее рациональное число, большее <tex>\beta</tex> по модулю (т.е. <tex> b_\beta \in \mathbb Q, |b_\beta| > |\beta| </tex>), то |
− | <tex> f_{\alpha \beta}(\varepsilon) = f_{\alpha}(\ | + | <tex> f_{\alpha \beta}(\varepsilon) = f_{\alpha}\left(\dfrac {\varepsilon} {b_\beta}\right) f_{\beta}\left(\dfrac {\varepsilon} {a}\right) </tex>. |
− | Убедимся в вычислимости числа <tex> \ | + | Убедимся в вычислимости числа <tex> \dfrac {1} {\alpha} </tex>: |
− | <tex> |\ | + | <tex> \left|\dfrac {1} {\alpha} - \dfrac{1}{a}\right| \leqslant \dfrac {|a - \alpha|}{a a_\alpha} </tex>, где <tex> a_\alpha \in \mathbb Q, |a_\alpha| < |\alpha| </tex>. |
− | <tex> f_{\frac 1 \alpha}(\varepsilon) = f_{\alpha}(\varepsilon a a_\alpha) </tex>. | + | <tex> f_{\frac {1} {\alpha}}(\varepsilon) = f_{\alpha}(\varepsilon a a_\alpha) </tex>. |
− | Отсюда, <tex> \ | + | Отсюда, <tex> \dfrac {\alpha} {\beta} = \dfrac{1} {\beta} \alpha </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= | ||
− | Предел вычислимо сходящейся вычислимой последовательности вычислимых чисел вычислим. | + | Предел вычислимо сходящейся вычислимой последовательности <tex> r_n </tex> вычислимых чисел вычислим. |
|proof= | |proof= | ||
− | Пусть | + | Пусть <tex> \alpha = \lim\limits_{n \to \infty} r_n </tex>. Запишем формально данные нам условия: |
<tex> \forall \varepsilon_1 > 0\ \forall n > 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> | ||
Строка 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>: | + | '''function''' <tex> a(\varepsilon) </tex>: |
− | n = <tex> N(\ | + | n = <tex> N\left(\dfrac {\varepsilon} {2}\right) + 1 </tex> |
− | '''return''' <tex> p_n(\ | + | '''return''' <tex> p_n\left(\dfrac {\varepsilon} {2}\right) </tex> |
− | Так как <tex> |\alpha - | + | Так как <tex> \left|\alpha - p_{n}\left(\dfrac {\varepsilon} {2}\right)\right| < |\alpha - r(n)| + \left|r(n) - p_n\left(\dfrac {\varepsilon} {2}\right)\right| </tex>, оба слагаемых меньше <tex> \dfrac {\varepsilon} {2} </tex> (первое {{---}} по выбору <tex> n </tex>, второе {{---}} в силу вычислимости <tex> p_n </tex>), то <tex> \left|\alpha - p_n\left(\dfrac \varepsilon 2\right)\right| < \varepsilon </tex>, и <tex> a(\varepsilon) </tex> действительно вычисляет требуемое приближение. |
}} | }} | ||
Строка 165: | Строка 165: | ||
{{Определение | {{Определение | ||
|definition= | |definition= | ||
− | Действительное число <tex> \alpha </tex> называется '''перечислимым снизу''' (recursively enumerable number), если множество <tex> \{ a \in \mathbb Q \mid a < \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>\iff</tex> существует вычислимая возрастающая последовательность рациональных чисел, пределом которой является <tex> \alpha </tex>. |
|proof= | |proof= | ||
− | <tex>\ | + | <tex>\Longrightarrow</tex> |
− | + | : По определению <tex> \alpha </tex>, множество <tex> A = \{ a \in \mathbb Q \mid a < \alpha \} </tex> перечислимо. Кроме того, <tex> \sup A = \alpha </tex>. | |
− | <tex>\ | + | : По определению нижней грани, <tex> \forall \varepsilon > 0\ \exists x_\varepsilon \in A: \varepsilon > \alpha - x_\varepsilon </tex>. Тогда можно взять, например, последовательность <tex> a_n = x_{\frac{1}{n}} </tex>. |
− | + | <tex>\Longleftarrow</tex> | |
− | + | : Построим полуразрешитель для множества <tex> A </tex>: | |
− | |||
− | |||
− | |||
− | Если <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>. | + | '''function''' <tex>p(x)</tex>: |
+ | '''for''' n = <tex>1</tex> '''to''' <tex>\infty</tex> | ||
+ | '''if''' <tex> x < a_n </tex> | ||
+ | '''return''' <tex>1</tex> | ||
+ | |||
+ | : Если <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> вычислимо <tex>\iff</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>. | ||
Строка 208: | Строка 210: | ||
== Последовательность Шпеккера == | == Последовательность Шпеккера == | ||
− | + | Множество всех программ счётно, поэтому множество вычислимых чисел также счётно. Однако, множество вещественных чисел несчётно, значит, существуют невычислимые вещественные числа. Построим явно пример такого числа. | |
{{Определение | {{Определение | ||
|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>, следовательно, она сходится по признаку Вейерштрасса. |
{{Теорема | {{Теорема | ||
Строка 223: | Строка 225: | ||
<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 - | + | * [[Рекурсивные функции]] |
− | * http://en.wikipedia.org/wiki/Computable_number | + | * [[Вычислимые функции]] |
− | * http://en.wikipedia.org/wiki/Specker_sequence | + | |
+ | == Источники информации == | ||
+ | * ''Верещагин Н. К., Шень А.'' {{---}} Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции — М.: МЦНМО, 1999 {{---}} стр. 14 | ||
+ | * [http://en.wikipedia.org/wiki/Computable_number Computable number] | ||
+ | * [http://en.wikipedia.org/wiki/Specker_sequence Specker sequence] | ||
+ | [[Категория: Теория формальных языков]] | ||
[[Категория: Теория вычислимости]] | [[Категория: Теория вычислимости]] | ||
− | [[Категория: | + | [[Категория: Разрешимые и перечислимые языки]] |
Текущая версия на 19:07, 4 сентября 2022
В математике натуральные, целые и рациональные числа являются конструктивными объектами, поэтому их использование в теории вычислимости не требует особых уточнений. В то же время, действительные числа, которые необходимы для применения методов математического анализа, определяются неконструктивно. Предложенный далее метод позволяет построить конструктивные объекты, во многом схожие с обычными действительными числами.
Вычислимые числа
Определение: |
Действительное число вычислимая функция , такая, что для любого рационального . | называется вычислимым (англ. computable number), если существует
Свойства
Теорема: |
Число разрешимо. вычислимо множество |
Доказательство: |
function: for to if return if return
function: for if return
|
Важное замечание: построенное нами доказательство неконструктивно, так как мы не знаем наперед, рационально ли число
, и уж тем более не пытаемся понять в случае его рациональности, чему именно оно равно. Но, так как мы ставим целью исследование свойств вычислимых чисел, а не явное построение соответствующих этим свойствам программ, то нам это доказательство полностью подходит.С учетом только что доказанной теоремы, далее при проверке на принадлежность числа
множеству будем писать просто .Теорема: |
Число вычислимо последовательность знаков представляющей его двоичной записи вычислима. |
Доказательство: |
function: for to if else return
|
Определение: |
Последовательность рациональных чисел | вычислимо сходится к , если существует вычислимая функция , такая, что для любого рационального выполняется .
Теорема: |
Число вычислимо существует вычислимая последовательность рациональных чисел, вычислимо сходящаяся к . |
Доказательство: |
|
Теорема: |
Пусть числа вычислимы. Тогда также вычислимы числа , , и . |
Доказательство: |
В пределах этого доказательства будем обозначать функцию-приближение для произвольного вычислимого числа как .Для того, чтобы получить приближение для результата операции, нам нужно выразить функцию-результат через приближения для операндов. Заметим, что , для произвольных рациональных , значит, в качестве необходимых функций для и можно взять
и
соответственно (при подстановке в неравенство и вместо и каждый модуль в правой части не превосходит , поэтому не превосходит ).Далее, так как , где — наименьшее рациональное число, большее по модулю (т.е. ), то. Убедимся в вычислимости числа :, где . Отсюда, . также вычислимо. |
Теорема: |
Корень многочлена с вычислимыми коэффициентами вычислим. |
Доказательство: |
Пусть — корень многочлена с вычислимыми коэффициентами.Если , то его можно найти точно, перебрав все рациональные числа.Иначе, выберем некоторый интервал ( — вычислимы), достаточно малый, чтобы полином был монотонным на отрезках и .Заметим, что для вычислимого значение также вычислимо, так как в процессе его вычисления используются только операции, вычислимость значений которых уже была ранее доказана.Теперь, если полином имеет разные знаки на отрезках Останавливая тот или иной алгоритм, когда текущая длина интервала становится меньше и , то для поиска можно воспользоваться двоичным поиском нуля на , иначе — троичным поиском экстремума на . и возвращая левую границу в качестве ответа, получаем функцию . |
Теорема: |
Предел вычислимо сходящейся вычислимой последовательности вычислимых чисел вычислим. |
Доказательство: |
Пусть . Запишем формально данные нам условия:
Здесь функции , и все вычислимы.Построим функцию , которая дает приближение к с точностью до :functionТак как : n = return , оба слагаемых меньше (первое — по выбору , второе — в силу вычислимости ), то , и действительно вычисляет требуемое приближение. |
Перечислимые числа
Определение: |
Действительное число перечислимо. | называется перечислимым снизу (англ. recursively enumerable number), если множество
Определение: |
Действительное число | называется перечислимым сверху, если множество перечислимо.
Свойства
Теорема: |
Число перечислимо снизу существует вычислимая возрастающая последовательность рациональных чисел, пределом которой является . |
Доказательство: |
function: for n = to if return
|
Теорема: |
Число вычислимо оно перечислимо сверху и снизу. |
Доказательство: |
Обозначим множества и за и соответственно.Если В противном случае, так как рационально, то необходимые (полу)разрешители строятся тривиально. , то перечислимость множеств и равносильна разрешимости множества , которая, в свою очередь, равносильна вычислимости . |
Последовательность Шпеккера
Множество всех программ счётно, поэтому множество вычислимых чисел также счётно. Однако, множество вещественных чисел несчётно, значит, существуют невычислимые вещественные числа. Построим явно пример такого числа.
Определение: |
Пусть | — некоторое перечислимое, но неразрешимое множество натуральных чисел. Пронумеруем его элементы. Последовательностью Шпеккера называется последовательность рациональных чисел, -ный член которой определяется как .
Данная последовательность строго возрастает и ограничена числом , следовательно, она сходится по признаку Вейерштрасса.
Теорема: |
Число перечислимо снизу, но невычислимо. |
Доказательство: |
перечислимо снизу, как предел возрастающей вычислимой последовательности рациональных чисел. Допустим теперь, что Пусть — вычислимо. . Рассмотрим двоичную запись числа , если ее -ный знак после запятой равен 1, то , иначе — . Мы построили разрешитель для множества . Тем не менее, известно, что — неразрешимое множество, а это невозможно, значит, — невычислимо. |
См. также
Источники информации
- Верещагин Н. К., Шень А. — Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции — М.: МЦНМО, 1999 — стр. 14
- Computable number
- Specker sequence