333
правки
Изменения
Нет описания правки
== Основные определения ==
{{Определение
|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>.
== Характеристика перечислимых множеств через вычислимые функции ==
{{Определение
|definition='''Множество <tex>X</tex> называется перечислимым'''('''computably enumerable set'''), если выполняется хотя бы одно из условий:
# существует программа, перечисляющая все элементы <tex>X</tex> в произвольном порядке;
# <tex>X</tex> является областью определения [[Вычислимые функции|вычиcлимой функции]] <tex>f</tex>;
}}
== Литература Источники ==
* Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. — М.: МЦНМО, 1999. с. 134, с. 176. ISBN 5-900916-36-7
* [http://en.wikipedia.org/wiki/Computable_function Wikipedia — Computable function]
* [http://en.wikipedia.org/wiki/Recursively_enumerable_set Wikipedia — Computably enumerable set]
* [http://ru.wikipedia.org/wiki/%D0%92%D1%8B%D1%87%D0%B8%D1%81%D0%BB%D0%B8%D0%BC%D0%B0%D1%8F_%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D1%8F Википедия — Вычислимая функция]
* [http://ru.wikipedia.org/wiki/%D0%9F%D0%B5%D1%80%D0%B5%D1%87%D0%B8%D1%81%D0%BB%D0%B8%D0%BC%D0%BE%D0%B5_%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2%D0%BE Википедия — Перечислимое множество]
[[Категория: Теория формальных языков]]
[[Категория: Теория вычислимости]]
