Изменения
Новая страница: «{{Определение |definition = Функция <tex>f : N \rightarrow N \cup \lbrace \bot \rbrace</tex> называется '''вычислимой''', ес...»
{{Определение
|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>.
}}
== Литература ==
* ''Верещагин Н. К., Шень А.'' '''Лекции по математической логике и теории алгоритов. Часть 3. Вычислимые функции''' -- М.: МЦНМО, 1999 - С. 176
|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>.
}}
== Литература ==
* ''Верещагин Н. К., Шень А.'' '''Лекции по математической логике и теории алгоритов. Часть 3. Вычислимые функции''' -- М.: МЦНМО, 1999 - С. 176
