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

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

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

Определение:

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

Свойства

Теорема:

Число [math] \alpha [/math] вычислимо тогда и только тогда, когда множество [math]A = \{x \in Q \mid x \lt \alpha \} [/math], разрешимо.

Доказательство:

[math]\triangleright[/math]

[math] \Longrightarrow [/math]: Построим разрешатель для [math] A [/math]: [math]p(x)[/math]: for [math] n = 1.. \infty [/math]: if [math] x \lt a(\frac1n) - \frac1n [/math]: return 1 if [math] x \gt a(\frac1n) + \frac1n [/math]: return 0 [math] \Longleftarrow [/math]: Построим функцию [math] a(\varepsilon) [/math]: [math] a(\varepsilon) [/math]: for [math] x \in A [/math]: if [math] x + \varepsilon \notin A [/math]: return x Так как [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] \alpha [/math]. TODO: вычислимо сходящаяся

Доказательство:

[math]\triangleright[/math]

[math] \Longrightarrow [/math]: [math] \Longleftarrow [/math]:

[math]\triangleleft[/math]

Теорема:

Пусть числа [math] \alpha, \beta [/math] вычислимы. Тогда также вычислимы числа [math] \alpha + \beta [/math], [math] \alpha - \beta [/math], [math] \alpha \beta [/math] и [math] \frac \alpha \beta [/math].

Доказательство:

[math]\triangleright[/math]

[math] \Longrightarrow [/math]: [math] \Longleftarrow [/math]:

[math]\triangleleft[/math]

Теорема:

Корень многочлена с вычислимыми коэффициентами вычислим.

Теорема:

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

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

Определение:

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

Аналогично определяются перечислимые сверху числа.

Свойства

Теорема:

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

Теорема:

Число [math] \alpha [/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] перечислимо снизу, но невычислимо.

Ссылки

• Верещагин Н. К., Шень А. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции — М.: МЦНМО, 1999 - С. 14
• http://en.wikipedia.org/wiki/Computable_number
• http://en.wikipedia.org/wiki/Specker_sequence