Вычислимые числа — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(начал пилить статью)
 
(не показано 38 промежуточных версий 2 участников)
Строка 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> \{a \in Q \mid a < \alpha \} </tex>, разрешимо.
+
Число <tex> \alpha </tex> вычислимо <tex>\iff</tex> множество <tex>A = \{x \in \mathbb Q \mid x < \alpha \} </tex> [[Разрешимые (рекурсивные) языки|разрешимо]].
 
|proof=
 
|proof=
 +
<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(\dfrac{1}{n} \right)  - \dfrac{1}{n} </tex>
 +
      '''return''' <tex>1</tex>
 +
    '''if''' <tex> x > a \left(\dfrac{1}{n} \right) + \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> x </tex> множеству <tex> A </tex> будем писать просто <tex> x < \alpha </tex>.
 +
 +
{{Теорема
 +
|statement=
 +
Число <tex> \alpha </tex> вычислимо <tex>\iff</tex> последовательность знаков представляющей его двоичной записи вычислима.
 +
|proof=
 +
<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> знаками после запятой.
 +
}}
 +
 +
{{Определение
 +
|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>.
 
}}
 
}}
  
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=
Число <tex> \alpha </tex> вычислимо тогда и только тогда, когда существует вычислимая последовательность рациональных чисел, вычислимо сходящаяся к <tex> \alpha </tex>. {{TODO|t=вычислимо сходящаяся}}
+
Число <tex> \alpha </tex> вычислимо <tex>\iff</tex> существует вычислимая последовательность рациональных чисел, вычислимо сходящаяся к <tex> \alpha </tex>.
 
|proof=
 
|proof=
 +
<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> вычислимо по определению.
 
}}
 
}}
  
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=
Пусть числа <tex> \alpha, \beta </tex> вычислимы. Тогда также вычислимы числа <tex> \alpha + \beta </tex>, <tex> \alpha - \beta </tex>, <tex> \alpha \beta </tex> и <tex> \frac \alpha \beta </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> |(\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}\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)| \leqslant |\beta||\alpha - a| + |a||\beta - b| \leqslant |b_\beta||\alpha - a| + |a||\beta - b|</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}\left(\dfrac {\varepsilon} {b_\beta}\right) f_{\beta}\left(\dfrac {\varepsilon} {a}\right) </tex>.
 +
 +
Убедимся в вычислимости числа <tex> \dfrac {1} {\alpha} </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> \dfrac {\alpha} {\beta} = \dfrac{1} {\alpha} \beta </tex> также вычислимо.
 +
 
}}
 
}}
  
Строка 31: Строка 127:
 
Корень многочлена с вычислимыми коэффициентами вычислим.
 
Корень многочлена с вычислимыми коэффициентами вычислим.
 
|proof=
 
|proof=
 +
Пусть <tex> x </tex> {{---}} корень многочлена <tex> P(x) </tex> с вычислимыми коэффициентами.
 +
 +
Если <tex> x \in \mathbb Q </tex>, то его можно найти точно, перебрав все рациональные числа.
 +
 +
Иначе, выберем некоторый интервал <tex> [a; b]: x \in [a; b] </tex> (<tex> a, b </tex> {{---}} вычислимы), достаточно малый, чтобы полином <tex> P(x) </tex> был монотонным на отрезках <tex> [a; x] </tex> и <tex> [x; b] </tex>.
 +
 +
Заметим, что для вычислимого <tex> t </tex> значение <tex> P(t) </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>.
 
}}
 
}}
  
 
{{Теорема
 
{{Теорема
 
|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 > (\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> N(\varepsilon_1) </tex>, <tex> r(n) </tex> и все <tex> p_n(\varepsilon_2) </tex> вычислимы.
 +
 +
Построим функцию <tex> a(\varepsilon) </tex>, которая дает приближение к <tex> \alpha </tex> с точностью до <tex> \varepsilon </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_{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> действительно вычисляет требуемое приближение.
 
}}
 
}}
  
Строка 43: Строка 165:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Действительное число <tex> \alpha </tex> называется '''перечислимым снизу''' (recursively enumerable number), если множество <tex> \{ a \in Q \mid a < \alpha \} </tex> перечислимо.
+
Действительное число <tex> \alpha </tex> называется '''перечислимым снизу''' (англ. ''recursively enumerable number''), если множество <tex> \{ a \in \mathbb Q \mid a < \alpha \} </tex> [[Перечислимые языки|перечислимо]].
 
}}
 
}}
  
Аналогично определяются перечислимые сверху числа.
+
{{Определение
 +
|definition=
 +
Действительное число <tex> \alpha </tex> называется '''перечислимым сверху''', если множество <tex> \{ a \in \mathbb Q \mid a > \alpha \} </tex> перечислимо.
 +
}}
  
 
=== Свойства ===
 
=== Свойства ===
Строка 52: Строка 177:
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=
Число <tex> \alpha </tex> перечислимо снизу тогда и только тогда, когда существует вычислимая возрастающая последовательность рациональных чисел, пределом которой является <tex> \alpha </tex>.
+
Число <tex> \alpha </tex> перечислимо снизу <tex>\iff</tex> существует вычислимая возрастающая последовательность рациональных чисел, пределом которой является <tex> \alpha </tex>.
 
|proof=
 
|proof=
 +
<tex>\Longrightarrow</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_{\frac{1}{n}} </tex>.
 +
 +
<tex>\Longleftarrow</tex>
 +
 +
: Построим полуразрешитель для множества <tex> A </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=
 +
Обозначим множества <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>.
 
}}
 
}}
  
 
== Последовательность Шпеккера ==
 
== Последовательность Шпеккера ==
 +
 +
Множество всех программ счётно, поэтому множество вычислимых чисел также счётно. Однако, множество вещественных чисел несчётно, значит, существуют невычислимые вещественные числа. Построим явно пример такого числа.
  
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Пусть <tex> A </tex> {{---}} некоторое перечислимое, но неразрешимое множество натуральных чисел. Занумеруем его элементы. '''Последовательностью Шпеккера''' <tex> \{q_n\} </tex> называется последовательность рациональных чисел, <tex>n</tex>-ный член которой определяется как <tex> q_n = \sum\limits_{k=1}^{n} 2^{-A(n)-1} </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>, следовательно, она сходится по признаку Вейерштрасса.
  
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=
 
Число <tex> q = \lim\limits_{n \to \infty} q_n </tex> перечислимо снизу, но невычислимо.
 
Число <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> {{---}} невычислимо.
 
}}
 
}}
  
== Ссылки ==
+
== См. также ==
* ''Верещагин Н. К., Шень А.'' Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции — М.: МЦНМО, 1999 - С. 14
+
* [[Рекурсивные функции]]
* 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]
  
 +
[[Категория: Теория формальных языков]]
 
[[Категория: Теория вычислимости]]
 
[[Категория: Теория вычислимости]]
[[Категория: Теория формальных языков]]
+
[[Категория: Разрешимые и перечислимые языки]]

Версия 23:10, 10 марта 2019

В математике натуральные, целые и рациональные числа являются конструктивными объектами, поэтому их использование в теории вычислимости не требует особых уточнений. В то же время, действительные числа, которые необходимы для применения методов математического анализа, определяются неконструктивно. Предложенный далее метод позволяет построить конструктивные объекты, во многом схожие с обычными действительными числами.

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

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


Свойства

Теорема:
Число [math] \alpha [/math] вычислимо [math]\iff[/math] множество [math]A = \{x \in \mathbb Q \mid x \lt \alpha \} [/math] разрешимо.
Доказательство:
[math]\triangleright[/math]

[math] \Longrightarrow [/math]

Если [math] \alpha [/math] — рациональное, то существует тривиальный разрешитель для [math] A [/math], который просто сравнивает полученный элемент с [math] \alpha [/math].
В противном случае, построим разрешитель для [math] A [/math]:
function [math] p(x)[/math]:
  for [math] n = 1[/math] to [math]\infty [/math]
    if [math] x \lt  a \left(\dfrac{1}{n} \right)  - \dfrac{1}{n} [/math]
      return [math]1[/math]
    if [math] x \gt  a \left(\dfrac{1}{n} \right) + \dfrac{1}{n} [/math]
      return [math]0[/math]

[math] \Longleftarrow [/math]

Построим функцию [math] a(\varepsilon) [/math]
function [math] a(\varepsilon) [/math]:
  for [math] x \in A [/math]
    if [math] x + \varepsilon \notin A [/math]
      return [math]x[/math]
Так как [math] A [/math] разрешимо, [math] \alpha = \sup A [/math] и для любого [math] x \in A [/math] проверка в условном операторе завершается за конечное время, то функция [math] a(\varepsilon) [/math] вычислима для любого рационального [math] \varepsilon [/math].
[math]\triangleleft[/math]

Важное замечание: построенное нами доказательство неконструктивно, так как мы не знаем наперед, рационально ли число [math] \alpha [/math], и уж тем более не пытаемся понять в случае его рациональности, чему именно оно равно. Но, так как мы ставим целью исследование свойств вычислимых чисел, а не явное построение соответствующих этим свойствам программ, то нам это доказательство полностью подходит.

С учетом только что доказанной теоремы, далее при проверке на принадлежность числа [math] x [/math] множеству [math] A [/math] будем писать просто [math] x \lt \alpha [/math].

Теорема:
Число [math] \alpha [/math] вычислимо [math]\iff[/math] последовательность знаков представляющей его двоичной записи вычислима.
Доказательство:
[math]\triangleright[/math]

[math] \Longrightarrow [/math]

Если число [math] \alpha [/math] — рациональное, то необходимую последовательность можно получить, воспользовавшись стандартным алгоритмом перевода числа в двоичную систему счисления. Рассмотрим случай, когда [math] \alpha \in \mathbb R \setminus \mathbb Q [/math].
Очевидно, двоичная запись целой части [math] \alpha [/math] всегда вычислима (так как множество чисел, меньших [math] \alpha [/math], разрешимо, то можно перебрать все целые числа в порядке возрастания их абсолютных величин и найти наибольшее число, меньшее [math] \alpha [/math]), поэтому будем считать, что [math] \alpha \in (0; 1) [/math].
Напишем программу, которая по числу [math] n [/math] вычисляет [math] n [/math]-ный знак после запятой в двоичном представлении числа [math] \alpha [/math] :
function [math]p(n)[/math]:
  [math]l = 0, r = 1 [/math]
  for [math] k = 1[/math] to [math]n [/math]
    [math] m = \dfrac{l+r}{2} [/math]
    if [math] m \lt  \alpha[/math]
      [math]l = m, t = 1[/math]
    else
      [math]r = m, t = 0[/math]
  return [math]t[/math]

[math] \Longleftarrow [/math]

Для любого рационального [math] \varepsilon \gt 0 [/math], найдем [math] n: 2^{-n} \lt \varepsilon [/math], тогда в качестве значения функции [math] a(\varepsilon) [/math] можно взять часть последовательности знаков двоичной записи [math] \alpha [/math] с [math] n [/math] знаками после запятой.
[math]\triangleleft[/math]


Определение:
Последовательность рациональных чисел [math] \{ r_n \} [/math] вычислимо сходится к [math] \alpha [/math], если существует вычислимая функция [math] N: \mathbb Q \rightarrow \mathbb N [/math], такая, что для любого рационального [math] \varepsilon \gt 0 [/math] выполняется [math]\forall n \gt N(\varepsilon): |r_n - \alpha| \lt \varepsilon [/math].


Теорема:
Число [math] \alpha [/math] вычислимо [math]\iff[/math] существует вычислимая последовательность рациональных чисел, вычислимо сходящаяся к [math] \alpha [/math].
Доказательство:
[math]\triangleright[/math]

[math] \Longrightarrow [/math]

Так как [math] \alpha [/math] вычислимо, то, согласно предыдущей теореме, вычислима и его двоичная запись. Пусть [math] r_n [/math] — часть последовательности знаков двоичной записи [math] \alpha [/math] с [math] n [/math] знаками после запятой. Данная последовательность вычислима, а также вычислимо сходится к [math] \alpha [/math], так как [math] N(\varepsilon) = \lceil -\log_2 \varepsilon \rceil[/math].

[math] \Longleftarrow [/math]

Пусть [math] a(\varepsilon) = r_{N(\varepsilon)} [/math], тогда [math] \alpha [/math] вычислимо по определению.
[math]\triangleleft[/math]
Теорема:
Пусть числа [math] \alpha, \beta [/math] вычислимы. Тогда также вычислимы числа [math] \alpha + \beta [/math], [math] \alpha - \beta [/math], [math] \alpha \beta [/math] и [math] \dfrac {\alpha} {\beta} [/math].
Доказательство:
[math]\triangleright[/math]

В пределах этого доказательства будем обозначать функцию-приближение для произвольного вычислимого числа [math] x [/math] как [math] f_x [/math].

Для того, чтобы получить приближение для результата операции, нам нужно выразить функцию-результат через приближения для операндов.

Заметим, что [math] |(\alpha \pm \beta) - (a \pm b)| \leqslant |\alpha - a| \pm |\beta - b| [/math], для произвольных рациональных [math] a, b [/math], значит, в качестве необходимых функций для [math] \alpha + \beta [/math] и [math] \alpha - \beta [/math] можно взять

[math] f_{\alpha + \beta}(\varepsilon) = f_{\alpha}\left(\dfrac {\varepsilon} {2}\right) + f_{\beta}\left(\dfrac {\varepsilon} {2}\right) [/math]

и

[math] f_{\alpha - \beta}(\varepsilon) = f_{\alpha}\left(\dfrac {\varepsilon} {2}\right) - f_{\beta}\left(\dfrac {\varepsilon} {2}\right) [/math]

соответственно (при подстановке в неравенство [math] f_{\alpha} [/math] и [math] f_{\beta} [/math] вместо [math] a [/math] и [math] b [/math] каждый модуль в правой части не превосходит [math] \dfrac {\varepsilon} {2} [/math], поэтому [math] f_{\alpha \pm \beta} [/math] не превосходит [math] \varepsilon [/math]).

Далее, так как

[math] |\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|[/math],

где [math]b_\beta[/math] — наименьшее рациональное число, большее [math]\beta[/math] по модулю (т.е. [math] b_\beta \in \mathbb Q, |b_\beta| \gt |\beta| [/math]), то

[math] f_{\alpha \beta}(\varepsilon) = f_{\alpha}\left(\dfrac {\varepsilon} {b_\beta}\right) f_{\beta}\left(\dfrac {\varepsilon} {a}\right) [/math].

Убедимся в вычислимости числа [math] \dfrac {1} {\alpha} [/math]:

[math] \left|\dfrac {1} {\alpha} - \dfrac{1}{a}\right| \leqslant \dfrac {|a - \alpha|}{a a_\alpha} [/math], где [math] a_\alpha \in \mathbb Q, |a_\alpha| \lt |\alpha| [/math].

[math] f_{\frac {1} {\alpha}}(\varepsilon) = f_{\alpha}(\varepsilon a a_\alpha) [/math].

Отсюда, [math] \dfrac {\alpha} {\beta} = \dfrac{1} {\alpha} \beta [/math] также вычислимо.
[math]\triangleleft[/math]
Теорема:
Корень многочлена с вычислимыми коэффициентами вычислим.
Доказательство:
[math]\triangleright[/math]

Пусть [math] x [/math] — корень многочлена [math] P(x) [/math] с вычислимыми коэффициентами.

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

Иначе, выберем некоторый интервал [math] [a; b]: x \in [a; b] [/math] ([math] a, b [/math] — вычислимы), достаточно малый, чтобы полином [math] P(x) [/math] был монотонным на отрезках [math] [a; x] [/math] и [math] [x; b] [/math].

Заметим, что для вычислимого [math] t [/math] значение [math] P(t) [/math] также вычислимо, так как в процессе его вычисления используются только операции, вычислимость значений которых уже была ранее доказана.

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

Останавливая тот или иной алгоритм, когда текущая длина интервала становится меньше [math] \varepsilon [/math] и возвращая левую границу в качестве ответа, получаем функцию [math] a_x(\varepsilon) [/math].
[math]\triangleleft[/math]
Теорема:
Предел вычислимо сходящейся вычислимой последовательности [math] r_n [/math] вычислимых чисел вычислим.
Доказательство:
[math]\triangleright[/math]

Пусть [math] \alpha = \lim\limits_{n \to \infty} r_n [/math]. Запишем формально данные нам условия:

[math] \forall \varepsilon_1 \gt 0\ \forall n \gt (\varepsilon_1): |r(n) - \alpha| \lt \varepsilon_1 [/math]

[math] \forall n\ \forall \varepsilon_2 \gt 0\ |r(n) - p_n(\varepsilon_2)| \lt \varepsilon_2 [/math]

Здесь функции [math] N(\varepsilon_1) [/math], [math] r(n) [/math] и все [math] p_n(\varepsilon_2) [/math] вычислимы.

Построим функцию [math] a(\varepsilon) [/math], которая дает приближение к [math] \alpha [/math] с точностью до [math] \varepsilon [/math]:

function [math] a(\varepsilon) [/math]:
  n = [math] N\left(\dfrac {\varepsilon} {2}\right) + 1 [/math]
  return [math] p_n\left(\dfrac {\varepsilon} {2}\right) [/math]
Так как [math] \left|\alpha - p_{n}\left(\dfrac {\varepsilon} {2}\right)\right| \lt |\alpha - r(n)| + \left|r(n) - p_n\left(\dfrac {\varepsilon} {2}\right)\right| [/math], оба слагаемых меньше [math] \dfrac {\varepsilon} {2} [/math] (первое — по выбору [math] n [/math], второе — в силу вычислимости [math] p_n [/math]), то [math] \left|\alpha - p_n\left(\dfrac \varepsilon 2\right)\right| \lt \varepsilon [/math], и [math] a(\varepsilon) [/math] действительно вычисляет требуемое приближение.
[math]\triangleleft[/math]

Перечислимые числа

Определение:
Действительное число [math] \alpha [/math] называется перечислимым снизу (англ. recursively enumerable number), если множество [math] \{ a \in \mathbb Q \mid a \lt \alpha \} [/math] перечислимо.


Определение:
Действительное число [math] \alpha [/math] называется перечислимым сверху, если множество [math] \{ a \in \mathbb Q \mid a \gt \alpha \} [/math] перечислимо.


Свойства

Теорема:
Число [math] \alpha [/math] перечислимо снизу [math]\iff[/math] существует вычислимая возрастающая последовательность рациональных чисел, пределом которой является [math] \alpha [/math].
Доказательство:
[math]\triangleright[/math]

[math]\Longrightarrow[/math]

По определению [math] \alpha [/math], множество [math] A = \{ a \in \mathbb Q \mid a \lt \alpha \} [/math] перечислимо. Кроме того, [math] \sup A = \alpha [/math].
По определению нижней грани, [math] \forall \varepsilon \gt 0\ \exists x_\varepsilon \in A: \varepsilon \gt \alpha - x_\varepsilon [/math]. Тогда можно взять, например, последовательность [math] a_n = x_{\frac{1}{n}} [/math].

[math]\Longleftarrow[/math]

Построим полуразрешитель для множества [math] A [/math]:
function [math]p(x)[/math]:
  for n = [math]1[/math] to [math]\infty[/math]
    if [math] x \lt  a_n [/math]
      return [math]1[/math]
Если [math] x \in A[/math], то [math] \alpha - x = t \gt 0 [/math], и так как [math] \exists N:\ \forall n \gt N |a_n - \alpha| \lt t [/math], то программа вернет ответ при [math] n \gt N [/math].
[math]\triangleleft[/math]
Теорема:
Число [math] \alpha [/math] вычислимо [math]\iff[/math] оно перечислимо сверху и снизу.
Доказательство:
[math]\triangleright[/math]

Обозначим множества [math] \{a \in \mathbb Q \mid a \lt \alpha \} [/math] и [math] \{a \in \mathbb Q \mid a \gt \alpha \} [/math] за [math] A [/math] и [math] B [/math] соответственно.

Если [math] \alpha [/math] рационально, то необходимые (полу)разрешители строятся тривиально.

В противном случае, так как [math] B = \mathbb Q \setminus A[/math], то перечислимость множеств [math] A [/math] и [math] B [/math] равносильна разрешимости множества [math] A [/math], которая, в свою очередь, равносильна вычислимости [math] \alpha [/math].
[math]\triangleleft[/math]

Последовательность Шпеккера

Множество всех программ счётно, поэтому множество вычислимых чисел также счётно. Однако, множество вещественных чисел несчётно, значит, существуют невычислимые вещественные числа. Построим явно пример такого числа.


Определение:
Пусть [math] A [/math] — некоторое перечислимое, но неразрешимое множество натуральных чисел. Пронумеруем его элементы. Последовательностью Шпеккера [math] \{q_n\} [/math] называется последовательность рациональных чисел, [math]n[/math]-ный член которой определяется как [math] q_n = \sum\limits_{k=1}^{n} 2^{-A(n)-1} [/math].


Данная последовательность строго возрастает и ограничена числом [math] 1 [/math], следовательно, она сходится по признаку Вейерштрасса.

Теорема:
Число [math] q = \lim\limits_{n \to \infty} q_n [/math] перечислимо снизу, но невычислимо.
Доказательство:
[math]\triangleright[/math]

[math] q [/math] перечислимо снизу, как предел возрастающей вычислимой последовательности рациональных чисел.

Допустим теперь, что [math] q [/math] — вычислимо.

Пусть [math] A = \{p \mid p(p) = 1\}[/math]. Рассмотрим двоичную запись числа [math] q [/math], если ее [math] n [/math]-ный знак после запятой равен 1, то [math] n \in A [/math], иначе — [math] n \notin A [/math]. Мы построили разрешитель для множества [math] A [/math]. Тем не менее, известно, что [math] A [/math] — неразрешимое множество, а это невозможно, значит, [math] q [/math] — невычислимо.
[math]\triangleleft[/math]

См. также

Источники информации

  • Верещагин Н. К., Шень А. — Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции — М.: МЦНМО, 1999 — стр. 14
  • Computable number
  • Specker sequence