275
правок
Изменения
м
→Основные определения
== Основные определения ==
{{Определение
|definition = Функция <tex>f : N \rightarrow N \cup \lbrace \bot \rbrace</tex> называется '''вычислимой''' ('англ. ''computable function'''), если существует программа, вычисляющая функцию <tex>f</tex>, такая, что:
* если <tex>f(n)</tex> определено для натурального числа <tex>n</tex>, то программа завершает свою работу на входе <tex>n</tex> и выводит <tex>f(n)</tex>;
* если <tex>f(n)</tex> не определено, то программа зависает на входе <tex>n</tex>.
