1632
правки
Изменения
м
rollbackEdits.php mass rollback
|author=1
|statement=
Существует [[Вычислимые функции#Основные определения | вычислимая функция]], не имеющая всюду определенного вычислимого продолжения.
|proof=
Рассмотрим функцию <tex>f(n) = U(n, n) + 1</tex>, где <tex>U(n, n)</tex> {{---}} [[Диагональный метод.|универсальная функция]].
Предположим, у нее существует всюду определенное продолжение <tex>g(n)</tex>. Это значит, что <tex>\Rightarrow f(n) \neq \bot \Rightarrow g(n) = f(n)</tex> и <tex>\forall n: \in \mathbb{N} \ g(n) \neq \bot </tex>.
По определению универсальной функции <tex>g(n) = U(i, n)</tex> для некоторого <tex>i</tex>. Тогда <tex>\Rightarrow g(i) = U(i, i)</tex>. Поскольку <tex>g(n)</tex> всюду определена, то <tex>U(i, i) \neq \bot</tex>. Значит, определено значение <tex>f(i)</tex> и <tex>g(i) = f(i) = U(i, i) + 1</tex>. Получили противоречие.
Таким образом, построенная функция <tex>f(n)</tex> не имеет всюду определенного вычислимого продолжения.
|author=2
|statement=
Существует [[Вычислимые функции#Основные определения | вычислимая функция]], значения которой принадлежат множеству <tex>\{0, 1, \bot\}</tex>, не имеющая всюду определенного вычислимого продолжения.
|proof=
Рассмотрим функцию
\end{cases}</tex>
Предположим, у нее существует всюду определенное продолжение <tex>g(n)= U(i, n)</tex> для некоторого <tex>i</tex>.
Поскольку <tex>g(n) = U(i, n)</tex> для некоторого <tex>i</tex>. всюду определена, то <tex>g(i) = U(i, i)\neq \bot</tex>. Поскольку <tex>g(n)</tex> всюду определена, то и определено значение <tex>Uf(i, i) \neq \bot</tex>. Но тогда по построению функции <tex>f(n)</tex> видим, что <tex>f(i) \neq U(i, i)</tex>. Получили противоречие.
}}
{{Теорема
|statement=
Существуют такие непересекающиеся перечислимые множества <tex>X'</tex> и <tex>Y'</tex>, что <tex>X' \cap Y' = \o</tex> и не существует таких разрешимых множеств <tex>X</tex> и <tex>Y</tex>, что <tex>X' \in subset X</tex>, <tex>Y' \in subset Y</tex>, <tex>X \cap Y = \ovarnothing</tex>, <tex>X \cup Y = \mathbb{N}</tex>. Такие множества <tex>X'</tex> и <tex>Y'</tex> называют '''неотделимыми''' (англ. ''inseparable sets'').
|proof=
Рассмотрим множества <tex>X' = \{n \mid f(n) = 0\}</tex> и <tex>Y' = \{n \mid f(n) = 1\}</tex>, где <tex>f(n)</tex> {{---}} функция из леммы 2.
Пусть существуют <tex>X</tex> и <tex>Y</tex>, удовлетворяющие указанным свойствам, тогда вычислима характеристическая функция <tex>g(n) = \begin{cases}
1, & n \in Y \\
0, & n \notin Y (n \in X)
\end{cases}</tex> множества <tex>Y</tex>.
Заметим, что <tex>g(n)</tex> всюду определена и является продолжением <tex>f(n)</tex>, что противоречит лемме 2.
}}
Неотделимые множества используются в доказательстве других фактов<ref>[http://www.mccme.ru/free-books/shen/shen-logic-part3-2.pdf Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. — М.: МЦНМО, 1999. с. 39, с. 63, c. 100. ISBN 5-900916-36-7]</ref>.
== Примечания ==
<references />
== Источники информации ==
* [http://en.wikipedia.org/wiki/Recursively_inseparable_sets Wikipedia {{---}} Recursively inseparable sets]
* Gasarch, William (1998), "A survey of recursive combinatorics", Handbook of recursive mathematics, Vol. 2, Stud. Logic Found. Math. 139, Amsterdam: North-Holland, pp. 1041–1176, MR 1673598
* Smullyan, Raymond M. (1958), "Undecidability and recursive inseparability", Zeitschrift für Mathematische Logik und Grundlagen der Mathematik 4: 143–147
[[Категория: Теория формальных языков]]
[[Категория: Теория вычислимости]]
