Вычислимые функции

Основные определения

Определение:

Функция [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]