Изменения

{{Теорема

|statement = Приведенные определения эквивалентны.

Напишем полуразрешающую программу для множества <tex>F</tex>.

<tex>p(\langle x, y\rangle):</tex>

'''return''' 1

Так как [[Вычислимые функции#Свойства вычислимой функции|область определения вычислимой функции перечислима]], то можно перебрать элементы области определения. Если алгоритм нашел нужную нам пару, то вернуть 1.<br/>

Напишем программу, вычисляющую функцию <tex>f</tex>.

<tex>f(n):</tex>