|
|
| Строка 1: |
Строка 1: |
| | == Основные определения == | | == Основные определения == |
| | {{Определение | | {{Определение |
| − | |definition = (1) Функция <tex>f : N \rightarrow N \cup \lbrace \bot \rbrace</tex> называется '''вычислимой''', если существует программа, вычисляющая функцию <tex>f</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>, то программа завершает свою работу на входе <tex>n</tex> и выводит <tex>f(n)</tex>; |
| − | # если <tex>f(n)</tex> не определено, то программа зависает на входе <tex>n</tex>.
| + | * если <tex>f(n)</tex> не определено, то программа зависает на входе <tex>n</tex>. |
| | }} | | }} |
| | + | |
| | {{Определение | | {{Определение |
| − | |definition = (2) Функция <tex>f : N \rightarrow N \cup \lbrace \bot \rbrace</tex> называется '''вычислимой''', если её график <tex>F = \lbrace \langle x, y\rangle | f(x)</tex> определено и равно <tex>y \rbrace</tex> является [[Перечислимые_языки|перечислимым]] множеством пар натуральных чисел. | + | |definition = Функция <tex>f : N \rightarrow N \cup \lbrace \bot \rbrace</tex> называется '''вычислимой''', если её график <tex>F = \lbrace \langle x, y\rangle | f(x)</tex> определено и равно <tex>y \rbrace</tex> является [[Перечислимые_языки|перечислимым]] множеством пар натуральных чисел. |
| | }} | | }} |
| | | | |
| | {{Теорема | | {{Теорема |
| − | |statement = Определения (1) и (2) эквивалентны. | + | |statement = Приведенные определения эквивалентны. |
| − | |proof = <tex>1 \Rightarrow 2</tex><br/> | + | |proof = <tex>\Rightarrow </tex><br/>. |
| | Напишем полуразрешающую программу для множества <tex>F</tex>. | | Напишем полуразрешающую программу для множества <tex>F</tex>. |
| − | <tex>p(\langle x, y\rangle)</tex> | + | <tex>p(\langle x, y\rangle):</tex> |
| | '''for''' <tex>a \in D(f)</tex> | | '''for''' <tex>a \in D(f)</tex> |
| − | '''if''' <tex>a == x \land f(a) == y</tex>
| |
| − | '''return''' 1
| |
| − | Так как [[#D(f)|область определения вычислимой функции перечислима]], то можно перебрать элементы области определения. Если алгоритм нашел нужную нам пару, то вернуть 1.<br/>
| |
| − | <tex>2 \Rightarrow 1</tex><br/>
| |
| − | Напишем программу, вычисляющую функцию <tex>f</tex>.
| |
| − | <tex>f(n)</tex>
| |
| − | '''for''' <tex>\langle x, y \rangle \in F</tex>
| |
| − | '''if''' <tex>x == n</tex>
| |
| − | '''return''' <tex>y</tex>
| |
| − | Так как <tex>F</tex> перечислимое множество, то можно перебрать элементы этого множества.
| |
| − | }}
| |
| − |
| |
| − | === Замечание ===
| |
| − | Входами и выходами программ могут быть не только натуральные числа, но и двоичные строки, пары натуральных чисел, конечные последовательности слов и т.п. Поэтому аналогичным образом можно определить понятие вычислимой функции для счётных множеств.
| |
| − |
| |
| − | === Примеры вычислимых функций ===
| |
| − | * Нигде не определённая функция вычислима.
| |
| − | <tex>p(x)</tex>
| |
| − | '''return''' <tex>\bot</tex>
| |
| − | * <tex>f(x) = x^2</tex>, где <tex>x</tex> — рациональное число.
| |
| − | <tex>p(x)</tex>
| |
| − | '''return''' <tex>x^2</tex>
| |
| − |
| |
| − | == Свойства вычислимой функции ==
| |
| − | {{Утверждение
| |
| − | |id = D(f)
| |
| − | |statement = <tex>f</tex> — вычислимая функция. Тогда <tex>D(f)</tex> — перечислимое множество, где <tex>D(f)</tex> — область определения функции <tex>f</tex>.
| |
| − | |proof =
| |
| − | Для доказательства достаточно написать полуразрешающую программу.
| |
| − | <tex>p(x)</tex>
| |
| − | <tex>f(x)</tex>
| |
| − | '''return''' 1
| |
| − | Если функция <tex>f</tex> определена на входе <tex>x</tex>, то <tex>x \in D(f)</tex>. Тогда необходимо вернуть 1. Иначе программа зависнет при вызове <tex>f(x)</tex>.
| |
| − | }}
| |
| − | {{Утверждение
| |
| − | |statement = <tex>f</tex> — вычислимая функция. Тогда <tex>E(f)</tex> — перечислимое множество, где <tex>E(f)</tex> — область значений функции <tex>f</tex>;
| |
| − | |proof =
| |
| − | Для доказательства достаточно написать полуразрешающую программу.
| |
| − | <tex>p(x)</tex>
| |
| − | '''for''' <tex>y \in D(f)</tex>
| |
| − | '''if''' <tex>x == f(y)</tex>
| |
| − | '''return''' 1
| |
| − | Так как <tex>D(f)</tex> перечислимо, то можно перебрать элементы этого множества. Если программа находит слово, то она возвращает 1.
| |
| − | }}
| |
| − | {{Утверждение
| |
| − | |statement = <tex>f</tex> — вычислимая функция, <tex>X</tex> — перечислимое множество. Тогда <tex>f(X)</tex> — перечислимое множество.
| |
| − | |proof =
| |
| − | Для доказательства достаточно написать полуразрешающую программу.
| |
| − | <tex>p(x)</tex>
| |
| − | '''for''' <tex>y \in D(f) \cap X</tex>
| |
| − | '''if''' <tex>x == f(y)</tex>
| |
| − | '''return''' 1
| |
| − | Из [[Замкнутость_разрешимых_и_перечислимых_языков_относительно_теоретико-множественных_и_алгебраических_операций|замкнутости перечислимых языков относительно операции пересечения]] следует, что элементы множества <tex>X \cap D(f)</tex> можно перебрать. Если программа находит слово, то она возвращает 1.
| |
| − | }}
| |
| − | {{Утверждение
| |
| − | |statement = <tex>f</tex> — вычислимая функция, <tex>X</tex> — перечислимое множество. Тогда <tex>f^{-1}(X)</tex> — перечислимое множество.
| |
| − | |proof =
| |
| − | Для доказательства достаточно написать полуразрешающую программу.
| |
| − | <tex>p(x)</tex>
| |
| − | '''if''' <tex>f(x) \in X</tex>
| |
| − | '''return''' 1
| |
| − | На проверке условия <tex>f(x) \in X</tex> программа может зависнут, если <tex>f(x)</tex> не определено или <tex>f(x) \notin X</tex>. Если <tex>f(x)</tex> не определено, то <tex>x \notin f^{-1}(X)</tex>. Условие <tex>f(x) \notin X</tex> можно проверить, так как <tex>X</tex> перечислимо.
| |
| − | }}
| |
| − |
| |
| − | == Теорема об униформизации ==
| |
| − | {{Теорема
| |
| − | |statement = Пусть <tex>F</tex> — перечислимое множество пар натуральных чисел. Тогда существует вычислимая функция <tex>f</tex>, определенная на тех и только тех <tex>x</tex>, для которых найдется <tex>y</tex>, при котором <tex>\langle x, y \rangle \in F</tex>, причем значение <tex>f(x)</tex> является одним из таких <tex>y</tex>.
| |
| − | |proof =
| |
| − | Напишем программу, вычисляющую функцию <tex>f</tex>.
| |
| − | <tex>f(x)</tex>
| |
| − | '''for''' <tex>\langle a, b \rangle \in F</tex>
| |
| − | '''if''' <tex>x == a</tex>
| |
| − | '''return''' <tex>b</tex>
| |
| − | Так как множество <tex>F</tex> перечислимо, то его элементы можно перебрать.
| |
| − | }}
| |
| − |
| |
| − | == Теорема о псевдообратной функции ==
| |
| − | {{Теорема
| |
| − | |statement = Для любой вычислимой функции <tex>f</tex> существует вычислимая функция <tex>g</tex>, являющаяся псевдообратной в следующем смысле: <tex>E(f) = D(g)</tex>, и при этом <tex>f(g(f(x))) = f(x)</tex> для всех <tex>x</tex>, при которых <tex>f(x)</tex> определена.
| |
| − | |proof =
| |
| − | Напишем программу, вычисляющую функцию <tex>g</tex>.
| |
| − | <tex>g(n)</tex>
| |
| − | '''for''' <tex>x \in D(f)</tex>
| |
| − | '''if''' <tex>f(x) == n</tex>
| |
| − | '''return''' <tex>x</tex>
| |
| − | Так как область определения вычислимой функции перечислима, то можно перебрать элементы области определения.
| |
| − | }}
| |
| − |
| |
| − | == Литература ==
| |
| − | * ''Верещагин Н. К., Шень А.'' '''Лекции по математической логике и теории алгоритов. Часть 3. Вычислимые функции''' — М.: МЦНМО, 1999 - С. 176
| |
