Материал из Викиконспекты
Основные определения
Определение: |
Функция [math]f : N \rightarrow N \cup \lbrace \bot \rbrace[/math] называется вычислимой, если существует программа, вычисляющая функцию [math]f[/math], такая, что:
- если [math]f(n)[/math] определено для натурального числа [math]n[/math], то программа завершает свою работу на входе [math]n[/math] и выводит [math]f(n)[/math];
- если [math]f(n)[/math] не определено, то программа зависает на входе [math]n[/math].
|
Определение: |
Функция [math]f : N \rightarrow N \cup \lbrace \bot \rbrace[/math] называется вычислимой, если её график [math]F = \lbrace \langle x, y\rangle | f(x)[/math] определено и равно [math]y \rbrace[/math] является перечислимым множеством пар натуральных чисел. |
{{Теорема
|statement = Приведенные определения эквивалентны.
|proof = [math]\Rightarrow [/math]
.
Напишем полуразрешающую программу для множества [math]F[/math].
[math]p(\langle x, y\rangle):[/math]
for [math]a \in D(f)[/math]