Изменения
→Примеры разрешимых множества
'''return''' 0
Так как число <tex>e</tex> иррационально, то ответ будет найден за конечное время.
}}
{{Утверждение
|statement=
множество тех <tex>n</tex>, для которых в числе <tex>\pi</tex> есть не менее <tex>n</tex> девяток подряд, разрешимо.
|proof=
Предположим, что в числе <tex>\pi</tex> встречается <tex>k</tex> девяток подряд, тогда, логично, что встречается и любое число девяток меньших <tex>k</tex>.
В таком случае, разрешитель будет выглядеть следующим образом:
<tex>p_k(i) {:} </tex>
'''if''' <tex>i \leq k </tex>
'''return''' 1
'''else'''
'''return''' 0
Рассмотрим все программы семейства:
<tex>p_0(i) {:} </tex>
'''return''' 1
<tex>p_1(i) {:} </tex>
'''if''' <tex>i \leq 1 </tex>
'''return''' 1
'''else'''
'''return''' 0
<tex>p_2(i) {:} </tex>
'''if''' <tex>i \leq k </tex>
'''return''' 1
'''else'''
'''return''' 0
<tex>\dots</tex>
<tex>p_n(i) {:} </tex>
'''if''' <tex>i \leq n </tex>
'''return''' 1
'''else'''
'''return''' 0
По доказанному выше, какая-то программа из этого семейства будет разрешителем для искомого множества. Значит, искомое множество разрешимо.
}}
