689
правок
Изменения
начал пилить статью
В математике натуральные, целые и рациональные числа являются конструктивными объектами, поэтому их использование в теории вычислимости не требует особых уточнений. В то же время, действительные числа, которые необходимы для применения методов математического анализа, определяются неконструктивно. Предложенный далее метод позволяет построить конструктивные объекты, во многом схожие с обычными действительными числами.
== Вычислимые числа ==
{{Определение
|definition=
Действительное число <tex> \alpha </tex> называется '''вычислимым''' (computable number), если существует вычислимая функция <tex> a: \mathbb Q \rightarrow \mathbb Q </tex>, такая, что <tex>|\alpha - a(\varepsilon)| < \varepsilon </tex> для любого рационального <tex> \varepsilon > 0 </tex>.
}}
=== Свойства ===
{{Теорема
|statement=
Число <tex> \alpha </tex> вычислимо тогда и только тогда, когда множество <tex> \{a \in Q \mid a < \alpha \} </tex>, разрешимо.
|proof=
}}
{{Теорема
|statement=
Число <tex> \alpha </tex> вычислимо тогда и только тогда, когда существует вычислимая последовательность рациональных чисел, вычислимо сходящаяся к <tex> \alpha </tex>. {{TODO|t=вычислимо сходящаяся}}
|proof=
}}
{{Теорема
|statement=
Пусть числа <tex> \alpha, \beta </tex> вычислимы. Тогда также вычислимы числа <tex> \alpha + \beta </tex>, <tex> \alpha - \beta </tex>, <tex> \alpha \beta </tex> и <tex> \frac \alpha \beta </tex>.
|proof=
}}
{{Теорема
|statement=
Корень многочлена с вычислимыми коэффициентами вычислим.
|proof=
}}
{{Теорема
|statement=
Предел вычислимо сходящейся вычислимой последовательности вычислимых чисел вычислим.
|proof=
}}
== Перечислимые числа ==
{{Определение
|definition=
Действительное число <tex> \alpha </tex> называется '''перечислимым снизу''' (recursively enumerable number), если множество <tex> \{ a \in Q \mid a < \alpha \} </tex> перечислимо.
}}
Аналогично определяются перечислимые сверху числа.
=== Свойства ===
{{Теорема
|statement=
Число <tex> \alpha </tex> перечислимо снизу тогда и только тогда, когда существует вычислимая возрастающая последовательность рациональных чисел, пределом которой является <tex> \alpha </tex>.
|proof=
}}
{{Теорема
|statement=
Число <tex> \alpha </tex> вычислимо тогда и только тогда, когда оно перечислимо сверху и снизу.
}}
== Последовательность Шпеккера ==
{{Определение
|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> 1 </tex>, следовательно, по признаку Вейерштрасса, она сходится.
{{Теорема
|statement=
Число <tex> q = \lim\limits_{n \to \infty} q_n </tex> перечислимо снизу, но невычислимо.
}}
== Ссылки ==
* ''Верещагин Н. К., Шень А.'' Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции — М.: МЦНМО, 1999 - С. 14
* http://en.wikipedia.org/wiki/Computable_number
* http://en.wikipedia.org/wiki/Specker_sequence
[[Категория: Теория вычислимости]]
[[Категория: Теория формальных языков]]
== Вычислимые числа ==
{{Определение
|definition=
Действительное число <tex> \alpha </tex> называется '''вычислимым''' (computable number), если существует вычислимая функция <tex> a: \mathbb Q \rightarrow \mathbb Q </tex>, такая, что <tex>|\alpha - a(\varepsilon)| < \varepsilon </tex> для любого рационального <tex> \varepsilon > 0 </tex>.
}}
=== Свойства ===
{{Теорема
|statement=
Число <tex> \alpha </tex> вычислимо тогда и только тогда, когда множество <tex> \{a \in Q \mid a < \alpha \} </tex>, разрешимо.
|proof=
}}
{{Теорема
|statement=
Число <tex> \alpha </tex> вычислимо тогда и только тогда, когда существует вычислимая последовательность рациональных чисел, вычислимо сходящаяся к <tex> \alpha </tex>. {{TODO|t=вычислимо сходящаяся}}
|proof=
}}
{{Теорема
|statement=
Пусть числа <tex> \alpha, \beta </tex> вычислимы. Тогда также вычислимы числа <tex> \alpha + \beta </tex>, <tex> \alpha - \beta </tex>, <tex> \alpha \beta </tex> и <tex> \frac \alpha \beta </tex>.
|proof=
}}
{{Теорема
|statement=
Корень многочлена с вычислимыми коэффициентами вычислим.
|proof=
}}
{{Теорема
|statement=
Предел вычислимо сходящейся вычислимой последовательности вычислимых чисел вычислим.
|proof=
}}
== Перечислимые числа ==
{{Определение
|definition=
Действительное число <tex> \alpha </tex> называется '''перечислимым снизу''' (recursively enumerable number), если множество <tex> \{ a \in Q \mid a < \alpha \} </tex> перечислимо.
}}
Аналогично определяются перечислимые сверху числа.
=== Свойства ===
{{Теорема
|statement=
Число <tex> \alpha </tex> перечислимо снизу тогда и только тогда, когда существует вычислимая возрастающая последовательность рациональных чисел, пределом которой является <tex> \alpha </tex>.
|proof=
}}
{{Теорема
|statement=
Число <tex> \alpha </tex> вычислимо тогда и только тогда, когда оно перечислимо сверху и снизу.
}}
== Последовательность Шпеккера ==
{{Определение
|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> 1 </tex>, следовательно, по признаку Вейерштрасса, она сходится.
{{Теорема
|statement=
Число <tex> q = \lim\limits_{n \to \infty} q_n </tex> перечислимо снизу, но невычислимо.
}}
== Ссылки ==
* ''Верещагин Н. К., Шень А.'' Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции — М.: МЦНМО, 1999 - С. 14
* http://en.wikipedia.org/wiki/Computable_number
* http://en.wikipedia.org/wiki/Specker_sequence
[[Категория: Теория вычислимости]]
[[Категория: Теория формальных языков]]
