Изменения
Нет описания правки
Заметим, что <tex>g(n)</tex> всюду определена и является продолжением <tex>f(n)</tex>, что противоречит лемме 2.
}}
== Примеры неотделимых множеств ==
* Пусть <tex>\phi</tex> вычислимая функция, тогда <tex>A = \{e : \phi_e(0) = 0 \}</tex> и <tex>B = \{e : \phi_e(0) = 1\}</tex> {{---}} неотделимые множества (Gasarch 1998, p. 1047).
* Пусть <tex>\phi</tex> Гёделева нумерация для формул в арифметики Пьяно, тогда <tex>A = \{\phi(\psi) : PA \vdash \psi \}</tex> и <tex>B = \{\phi(\psi) : PA \vdash \neg\psi \}</tex> {{---}} неотделимые множества (Smullyan 1958).
== Решаемые задачи ==
{{Определение
|definition = '''Полное двоичное дерево''' {{---}} множество всех двоичных слов (конечных последовательностей нулей и единиц); его элементы называют вершинами дерева; пустое слово является корнем этого дерева, а слова <tex>x_0</tex> и <tex>x_1</tex> являются сыновьями вершины <tex>x</tex>, которая является отцом своих сыновей. Поддеревом полного двоичного дерева называют множество вершин, которое вместе с каждой вершиной содержит её отца.
}}
{{Лемма
|author=Кёниг
|statement=Бесконечное поддерево всегда имеет бесконечную ветвь (последовательность вершин, в которой каждая следующая является сыном предыдущей).
}}
Можно показать, что эффективный вариант леммы Кёнига неверен: существует бесконечное разрешимое поддерево полного двоичного дерева, не имеющее вычислимой бесконечной ветви. (Взяв пару перечислимых неотделимых множеств, можно построить дерево, в котором любая бесконечная ветвь поворачивает направо в точках первого множества и налево в точках второго. При этом поддерево можно сделать разрешимым, так как запрет поворота можно наложить на произвольно высоком уровне, когда выяснится принадлежность одному из множеств).
== Источники информации ==
* Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. — М.: МЦНМО, 1999. с. 20, с. 68. ISBN 5-900916-36-7
* [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
[[Категория: Теория формальных языков]]
[[Категория: Теория вычислимости]]
