205
правок
Изменения
Нет описания правки
{{Определение
|definition = Функция <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>.
}}
''Замечание''<br/>
Входами и выходами программ могут быть не только натуральные числа, но и двоичные строки, пары натуральных чисел, конечные последовательности слов и т.п. Поэтому аналогичным образом можно определить понятие вычислимой функции для рациональных чисел.
=== Примеры вычислимых функций ===
* Нигде не определённая функция вычислима.
p(x)
'''return''' <tex>\bot</tex>
* <tex>f(x) = x^2</tex>, где <tex>x</tex> — рациональное число.
p(x)
'''return''' <tex>x^2</tex>
== Литература ==
* ''Верещагин Н. К., Шень А.'' '''Лекции по математической логике и теории алгоритов. Часть 3. Вычислимые функции''' -- М.: МЦНМО, 1999 - С. 176
