Изменения

Действительное число <tex> \alpha </tex> называется '''вычислимым''' (англ. ''computable number''), если существует [[Вычислимые функции|вычислимая функция]] <tex> a(\varepsilon): \mathbb Q \rightarrow \mathbb Q </tex>, такая, что <tex>|\alpha - a(\varepsilon)| < \varepsilon </tex> для любого рационального <tex> \varepsilon > 0 </tex>.

Число <tex> \alpha </tex> вычислимо тогда и только тогда, когда <tex>\iff</tex> множество <tex>A = \{x \in \mathbb Q \mid x < \alpha \} </tex> [[Разрешимые (рекурсивные) языки|разрешимо]].

<tex> \Longrightarrow </tex>:

: Если <tex> \alpha </tex> {{---}} рациональное, то существует тривиальный разрешитель для <tex> A </tex>, который просто сравнивает полученный элемент с <tex> \alpha </tex>.

: В противном случае, построим разрешитель для <tex> A </tex>:

'''function''' <tex>p(x)</tex>: '''for''' <tex> n = 1.. </tex> '''to''' <tex>\infty </tex>: '''if''' <tex> x < a\left(\dfrac1ndfrac{1}{n} \right) - \dfrac1n dfrac{1}{n} </tex>: '''return''' <tex>1</tex> '''if''' <tex> x > a\left(\dfrac1ndfrac{1}{n} \right) + \dfrac1n dfrac{1}{n} </tex>: '''return''' <tex>0</tex>

<tex> \Longleftarrow </tex>:

: Построим функцию <tex> a(\varepsilon) </tex>:

'''function''' <tex> a(\varepsilon) </tex>: '''for''' <tex> x \in A </tex>: '''if''' <tex> x + \varepsilon \notin A </tex>: '''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> \alpha </tex> вычислимо тогда и только тогда, когда <tex>\iff</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> после запятой:

'''function''' <tex>p(n)</tex>: <tex>l = 0, r = 1</tex> '''for''' <tex> k = 1..</tex> '''to''' <tex>n </tex>: <tex> m = \dfrac{l+r}{2 } </tex> '''if''' <tex> m < \alpha</tex>: <tex>l = m, t = 1</tex> '''else''': <tex>r = m, t = 0</tex> '''return''' <tex>t</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> \{ 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> \alpha </tex> вычислимо тогда и только тогда, когда <tex>\iff</tex> существует вычислимая последовательность рациональных чисел, вычислимо сходящаяся к <tex> \alpha </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> a(\varepsilon) = r_{N(\varepsilon)} </tex>, тогда <tex> \alpha </tex> вычислимо по определению.

Пусть числа <tex> \alpha, \beta </tex> вычислимы. Тогда также вычислимы числа <tex> \alpha + \beta </tex>, <tex> \alpha - \beta </tex>, <tex> \alpha \beta </tex> и <tex> \dfrac {\alpha } {\beta } </tex>.

Заметим, что <tex> |(\alpha \pm \beta) - (a \pm b)| \le 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}\left(\dfrac {\varepsilon } {2}\right) + f_{\beta}\left(\dfrac {\varepsilon } {2}\right) </tex>

<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> \dfrac {\varepsilon } {2 } </tex>, поэтому, <tex> f_{\alpha \pm \beta} </tex> не превосходит <tex> \varepsilon </tex>).

<tex> |\alpha \beta - ab| = |(\alpha \beta - a \beta) + (a \beta - ab)| \le leqslant |\beta||\alpha - a| + |a||\beta - b| \le leqslant |b_\beta||\alpha - a| + |a||\beta - b|</tex>,

где <tex> b_\beta \in Q</tex> {{---}} наименьшее рациональное число, |b_\beta| большее <tex> |\beta| </tex> по модулю (т.е. <tex> b_\beta \in \mathbb Q, |b_\beta| > |\beta| </tex>, очевидно, можно найти за конечное время), то

<tex> f_{\alpha \beta}(\varepsilon) = f_{\alpha}\left(\dfrac {\varepsilon } {b_\beta}\right) f_{\beta}\left(\dfrac {\varepsilon } {a}\right) </tex>.

Убедимся в вычислимости числа <tex> \dfrac {1 } {\alpha } </tex>:

<tex> \left|\dfrac {1 } {\alpha } - \dfrac1adfrac{1}{a}\right| \le leqslant \dfrac {|a - \alpha|}{a a_\alpha} </tex>, где <tex> a_\alpha \in \mathbb Q, |a_\alpha| < |\alpha| </tex>.

<tex> f_{\dfrac frac {1 } {\alpha}}(\varepsilon) = f_{\alpha}(\varepsilon a a_\alpha) </tex>.

Отсюда, <tex> \dfrac {\alpha } {\beta } = \dfrac1 dfrac{1} {\alpha } \beta </tex> также вычислимо.

Если <tex> x \in \mathbb Q </tex>, то его можно найти точно, перебрав все рациональные числа.

Теперь, если полином имеет разные знаки на отрезках <tex> [a; x] </tex> и <tex> [x; b] </tex>, то для поиска <tex> x </tex> можно воспользоваться двоичным поиском для поиска нуля на <tex> [a; b] </tex>, иначе {{---}} троичным поиском для поиска минимума или максимума экстремума на <tex> [a; b] </tex>.

Предел вычислимо сходящейся вычислимой последовательности <tex> r_n </tex> вычислимых чисел вычислим.

Пусть рассматриваемая последовательность {{---}} <tex> r_n </tex>, и <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>

'''function''' <tex> a(\varepsilon) </tex>: n = <tex> N\left(\dfrac {\varepsilon } {2}\right) + 1 </tex> '''return''' <tex> p_n\left(\dfrac {\varepsilon } {2}\right) </tex>

Так как <tex> \left|\alpha - p_np_{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> действительно вычисляет требуемое приближение.

Действительное число <tex> \alpha </tex> называется '''перечислимым снизу''' (англ. ''recursively enumerable number''), если множество <tex> \{ a \in \mathbb Q \mid a < \alpha \} </tex> [[Перечислимые языки|перечислимо]].

Действительное число <tex> \alpha </tex> называется '''перечислимым сверху''', если множество <tex> \{ a \in \mathbb Q \mid a > \alpha \} </tex> перечислимо.

Число <tex> \alpha </tex> перечислимо снизу тогда и только тогда, когда <tex>\iff</tex> существует вычислимая возрастающая последовательность рациональных чисел, пределом которой является <tex> \alpha </tex>.

<tex>\RightarrowLongrightarrow</tex>:

: По определению <tex> \alpha </tex>, множество <tex> A = \{ a \in \mathbb Q \mid a < \alpha \} </tex> перечислимо. Кроме того, <tex> \sup A = \alpha </tex>.

: По определению нижней грани, <tex> \forall \varepsilon > 0\ \exists x_\varepsilon \in A: \varepsilon > \alpha - x_\varepsilon </tex>. Тогда можно взять, например, последовательность <tex> a_n = x_{\dfrac frac{1 }{n}} </tex>.

<tex>\LeftarrowLongleftarrow</tex>:

: Построим полуразрешитель для множества <tex> A </tex>:

'''function''' <tex>p(x)</tex>: '''for''' n in = <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>.

Число <tex> \alpha </tex> вычислимо тогда и только тогда, когда <tex>\iff</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> B = \mathbb Q \setminus A</tex>, то перечислимость множеств <tex> A </tex> и <tex> B </tex> равносильна разрешимости множества <tex> A </tex>, которая, в свою очередь, равносильна вычислимости <tex> \alpha </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> 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]

[[Категория: Теория формальных языковРазрешимые и перечислимые языки]]