36
правок
Изменения
Нет описания правки
== Основные определения ==
{{Определение
|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>f : N \rightarrow N \cup \lbrace \bot \rbrace</tex> называется '''вычислимой''', если её график <tex>F = \lbrace \langle x, y\rangle | \mid f(x)</tex> определено и равно <tex>y \rbrace</tex> является [[Перечислимые_языки|перечислимым]] множеством пар натуральных чисел.
}}
{{Теорема
|statement = Приведенные определения эквивалентны.
|proof = <tex>\Rightarrow </tex><br/>.
Напишем полуразрешающую программу для множества <tex>F</tex>.
<tex>p(\langle x, y\rangle):</tex>
'''return''' 1
Так как [[Вычислимые функции#Свойства вычислимой функции|область определения вычислимой функции перечислима]], то можно перебрать элементы области определения. Если алгоритм нашел нужную нам пару, то вернуть 1.<br/>
<tex>\Leftarrow</tex><br/>.
Напишем программу, вычисляющую функцию <tex>f</tex>.
<tex>f(n):</tex>
== Характеристика перечислимых множеств через вычислимые функции ==
{{Определение
|definition='''Множество <tex>X</tex> называется перечислимым''' ('англ. ''computably enumerable set'''), если выполняется хотя бы одно из условий:
# существует программа, перечисляющая все элементы <tex>X</tex> в произвольном порядке;
# <tex>X</tex> является областью определения [[Вычислимые функции|вычиcлимой функции]] <tex>f</tex>;
Определения ''1'', ''2'', ''3'', ''4'' эквивалентны.
|proof=
*1 <tex>1 \Rightarrow4</tex> 4.
Пусть <tex>p</tex> — программа, перечисляющая <tex>X</tex>.
*2 <tex>2 \Rightarrow1</tex> 1.
Пусть <tex>X</tex> — область определения вычислимой функции <tex>f</tex>, вычисляемой программой <tex>p</tex>.
'''print''' <tex>k</tex>
*3 <tex>3 \Rightarrow1</tex> 1.
Пусть <tex>X</tex> — область значений вычислимой функции <tex>f</tex>, вычисляемой программой <tex>p</tex>.
*4 <tex>4 \Rightarrow2</tex> 2, 4 <tex>4 \Rightarrow3</tex> 3.
Пусть дана <tex>f_X(x)</tex>.
}}
== См. также == * [[Рекурсивные функции]]* [[Вычислимые числа]]* [[Универсальная функция]] == Источники информации ==
* Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. — М.: МЦНМО, 1999. с. 134, с. 176. ISBN 5-900916-36-7
* [http://en.wikipedia.org/wiki/Computable_function Wikipedia — Computable function]
[[Категория: Теория формальных языков]]
[[Категория: Теория вычислимости]]
[[Категория: Разрешимые и перечислимые языки]]
