129
правок
Изменения
м
Нет описания правки
{{Определение
|definition=
Действительное число <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> A </tex>:
'''fun'''<tex>p(x)</tex>:
'''for''' <tex> n = 1.. \infty </tex>:
'''if''' <tex> x < a(\dfrac1n) - \dfrac1n </tex>:
Построим функцию <tex> a(\varepsilon) </tex>:
'''fun''' <tex> a(\varepsilon) </tex>:
'''for''' <tex> x \in A </tex>:
'''if''' <tex> x + \varepsilon \notin A </tex>:
Напишем программу, которая по числу <tex> n </tex> вычисляет <tex> n </tex>-ный знак числа <tex> \alpha </tex> после запятой:
'''fun''' <tex>p(n)</tex>:
l = 0, r = 1
'''for''' <tex> k = 1..n </tex>:
Построим функцию <tex> a(\varepsilon) </tex>, которая дает приближение к <tex> \alpha </tex> с точностью до <tex> \varepsilon </tex>:
'''fun''' <tex> a(\varepsilon) </tex>:
n = <tex> N(\dfrac \varepsilon 2) + 1 </tex>
'''return''' <tex> p_n(\dfrac \varepsilon 2) </tex>
Построим полуразрешитель для множества <tex> A </tex>:
'''fun''' <tex>p(x)</tex>:
'''for''' n in <tex>1..\infty</tex>:
'''if''' <tex> x < a_n </tex>:
