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

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

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

Литература

• Верещагин Н. К., Шень А. Лекции по математической логике и теории алгоритов. Часть 3. Вычислимые функции -- М.: МЦНМО, 1999 - С. 176