205
правок
Изменения
м
''=== Замечание''<br/>===Входами и выходами программ могут быть не только натуральные числа, но и двоичные строки, пары натуральных чисел, конечные последовательности слов и т.п. Поэтому аналогичным образом можно определить понятие вычислимой функции для счетных счётных множеств.
Нет описания правки
{{Определение
|definition = (1) Функция <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>.
}}
}}
{{Теорема
}}
{{Утверждение
|statement = <tex>f</tex> — вычислимая функция. Тогда <tex>E(f)</tex> — перечислимое множество, где <tex>E(f)</tex> — область изменения значений функции <tex>f</tex>;
|proof =
Для доказательства достаточно написать полуразрешающую программу.
