205
правок
Изменения
м
→Основные определения
|statement = Определения (1) и (2) эквивалентны.
|proof = <tex>1 \Rightarrow 2</tex><br/>
Напишем полуразрешающую программу полуразрешающую для множества <tex>F</tex>. p(<tex>p(\langle x, y\rangle)</tex>)
'''for''' <tex>a \in D(f)</tex>
'''if''' <tex>a == x && f(a) == y</tex>
'''then return''' 1
Так как [[#D(f)|область определения вычислимой функции перечислима]], то можно перебрать элементы области определения. Если алгоритм нашел нужную нам пару, то вернуть 1.<br/>
<tex>2 \Rightarrow 1</tex><br/>
Напишем программу, вычисляющую функцию <tex>f</tex>. <tex>f(n)</tex>
'''for''' <tex>\langle x, y \rangle \in F</tex>
'''if''' <tex>x == n</tex> '''then return''' <tex>y</tex>
Так как <tex>F</tex> перечислимое множество, то можно перебрать элементы этого множества.
}}
