205
правок
Изменения
Нет описания правки
== Основные определения ==
{{Определение
|definition = (1) Функция <tex>f : N \rightarrow N \cup \lbrace \bot \rbrace</tex> называется '''вычислимой''', если существует программа, вычисляющая функцию <tex>f</tex>. То есть существует такая программа, что:
# если <tex>f(n)</tex> определено для натурального числа <tex>n</tex>, то программа заканчивается на входе <tex>n</tex> и выводит <tex>f(n)</tex>;
# если <tex>f(n)</tex> не определено, то программа зависает на входе <tex>n</tex>.
}}
{{Определение
|definition = (2) Функция <tex>f : N \rightarrow N \cup \lbrace \bot \rbrace</tex> называется '''вычислимой''', если её график <tex>F = \lbrace \langle x, y\rangle | f(x)</tex> определено и равно <tex>y \rbrace</tex> является [[Перечислимые_языки|перечислимым]] множеством пар натуральных чисел.
}}
''Замечание''<br/>
Входами и выходами программ могут быть не только натуральные числа, но и двоичные строки, пары натуральных чисел, конечные последовательности слов и т.п. Поэтому аналогичным образом можно определить понятие вычислимой функции для счетных множеств.
p(x)
'''return''' <tex>x^2</tex>
{{Теорема
|statement = Определения (1) и (2) эквивалентны.
|proof = <tex>1 \Rightarrow 2</tex><br/>
Напишем программу полуразрешающую <tex>F</tex>.
p(<tex>\langle x, y\rangle</tex>)
'''for''' <tex>a \in D(f)</tex>
'''if''' a == x && f(a) == y
'''then return''' 1
Так как [[#D(f)|область определения вычислимой функции перечислимо]], то можно перебрать элементы области определения.<br/>
<tex>2 \Rightarrow 1</tex><br/>
Напишем программу, вычисляющую <tex>f</tex>.
f(n)
'''for''' <tex>\langle x, y \rangle \in F</tex>
'''if''' x == n
'''then return''' y
Так как <tex>F</tex> перечислимое множество, то можно перебрать элементы этого множества.
}}
== Свойства вычислимой функции ==
{{Утверждение
|id = D(f)|statement = <tex>f</tex> — вычислимая функция. Тогда <tex>D(f)</tex> — [[Перечислимые_языки|перечислимое]] множество, где <tex>D(f)</tex> — область определения функции <tex>f</tex>.
|proof =
Для доказательства достаточно написать полуразрешающую программу.
