689
правок
Изменения
→Свойства: доказательство теоремы 1
{{Теорема
|statement=
Число <tex> \alpha </tex> вычислимо тогда и только тогда, когда множество <tex> A = \{a x \in Q \mid a x < \alpha \} </tex>, разрешимо.
|proof=
<tex> \Longrightarrow </tex>:
Построим разрешатель для <tex> A </tex>:
<tex>p(x)</tex>:
'''for''' <tex> n = 1.. \infty </tex>:
'''if''' <tex> x < a(\frac1n) - \frac1n </tex>:
'''return''' 1
'''if''' <tex> x > a(\frac1n) + \frac1n </tex>:
'''return''' 0
<tex> \Longleftarrow </tex>:
Построим функцию <tex> a(\varepsilon) </tex>:
<tex> a(\varepsilon) </tex>:
'''for''' <tex> x \in A </tex>:
'''if''' <tex> x + \varepsilon \notin A </tex>:
'''return''' x
Так как <tex> A </tex> разрешимо, <tex> \alpha = \sup A </tex> и для любого <tex> x \in A </tex> проверка в условном операторе завершается за конечное время, то функция <tex> a(\varepsilon) </tex> вычислима для любого рационального <tex> \varepsilon </tex>.
}}
Число <tex> \alpha </tex> вычислимо тогда и только тогда, когда существует вычислимая последовательность рациональных чисел, вычислимо сходящаяся к <tex> \alpha </tex>. {{TODO|t=вычислимо сходящаяся}}
|proof=
<tex> \Longrightarrow </tex>:
<tex> \Longleftarrow </tex>:
}}
Пусть числа <tex> \alpha, \beta </tex> вычислимы. Тогда также вычислимы числа <tex> \alpha + \beta </tex>, <tex> \alpha - \beta </tex>, <tex> \alpha \beta </tex> и <tex> \frac \alpha \beta </tex>.
|proof=
<tex> \Longrightarrow </tex>:
<tex> \Longleftarrow </tex>:
}}
