205
правок
Изменения
м
=== Примеры вычислимых функций ===
* Нигде не определённая функция вычислима.
p(x)
'''return''' <tex>\bot</tex>
* <tex>f(x) = x^2</tex>, где <tex>x</tex> — рациональное число.
p(x)
'''return''' <tex>x^2</tex>
→Примеры вычислимых функций
''Замечание''<br/>
Входами и выходами программ могут быть не только натуральные числа, но и двоичные строки, пары натуральных чисел, конечные последовательности слов и т.п. Поэтому аналогичным образом можно определить понятие вычислимой функции для счетных множеств.
{{Теорема
'''if''' a == x && f(a) == y
'''then return''' 1
Так как [[#D(f)|область определения вычислимой функции перечислимоперечислима]], то можно перебрать элементы области определения. Если алгоритм нашел нужную нам пару, то вернуть 1.<br/>
<tex>2 \Rightarrow 1</tex><br/>
Напишем программу, вычисляющую <tex>f</tex>.
Так как <tex>F</tex> перечислимое множество, то можно перебрать элементы этого множества.
}}
=== Примеры вычислимых функций ===
* Нигде не определённая функция вычислима.
p(x)
'''return''' <tex>\bot</tex>
* <tex>f(x) = x^2</tex>, где <tex>x</tex> — рациональное число.
p(x)
'''return''' <tex>x^2</tex>
== Свойства вычислимой функции ==
