1632
правки
Изменения
м
# <tex>A\le_{m}A</tex>.{Утверждение|about=рефлексивность# Если <tex>A\le_{m}B</tex> и <tex>B</tex> разрешимо, то <tex>A</tex> разрешимо.|statement=# Если <tex>A\le_leqslant_{m}B</tex> и <tex>B</tex> перечислимо, то <tex>A</tex> перечислимо.# Если |proof=<tex>A\le_{m}B</tex> и <tex>B\le_{m}C</tex>, то <tex>A\le_{m}Cf(x)=x</tex>.# Если <tex>A\le_{m}B</tex>, то <tex>\overline{A}\le_{m}\overline{B}</tex>.
Если <tex>B</tex> неразрешимоСледует из второго свойства. }} Приведённая лемма позволяет доказывать алгоритмическую неразрешимость некоторой задачи, то для любого разрешимого <tex>X: X\ne B</tex>. Пусть мы хотим найти точкусводя к ней ''(а не наоборот!)'' другую, в неразрешимость которой уже доказана. ===Примеры применения==={{main|Примеры неразрешимых задач: проблема соответствий Поста|Примеры неразрешимых задач: задача о замощении}} ==Сведение по Тьюрингу=={{Определение|definition=Язык <tex>XL</tex> отличается от '''сводится по Тьюрингу''' (англ. ''Turing reducible'') к языку <tex>BM</tex>. Рассмотрим , если язык <tex>fL</tex> которая m-сводит является разрешимым с использованием <tex>AM</tex> к как оракула, обозначается как <tex>BL \leqslant_T M</tex>. }} {{Определение|definition=Язык <tex>f^{-1}(X)L</tex> будет разрешимым, как прообраз разрешимого множества'''эквивалентен по Тьюрингу''' (англ. Поэтому можно найти точку ''Turing equivalent'') языку <tex>xM</tex>, в которой если <tex>XL \leqslant_T M</tex> отличается от и <tex>AM \leqslant_T L</tex>. Тогда , обозначается как <tex>B</tex> будет отличаться от <tex>X</tex> в точке <tex>f(x)L \equiv_T M</tex>.
rollbackEdits.php mass rollback
{{Определение
|definition=Множество натуральных чисел <tex>A</tex> '''<tex>\textbf m</tex>-сводится''' (англ. ''many-one reducible'', ''m-reducible'') ко множеству натуральных чисел <tex>B</tex>, если существует всюду определённая [[Вычислимые функции|вычислимая функция ]] <tex>f:x\mathbb{N}in A\rightarrowLeftrightarrow f(x)\mathbb{N}in B</tex> со свойством , то есть <tex>\forall{x}:x\in f(A) \Leftrightarrow subset B</tex> и <tex>f(x\overline{A})\in subset \overline{B}</tex>. Обозначение: <tex>A\le_leqslant_{m}B</tex>.
}}
{{Определение
|definition=<tex>A</tex> '''<tex>\textbf m</tex>-эквивалентно''' (англ. ''many-one equivalent'', ''m-equivalent'') <tex>B</tex>, если <tex>A\le_leqslant_{m}B</tex> и <tex>B\le_leqslant_{m}A</tex>. Обозначение: <tex>A\equiv_{m}B</tex>.
}}
== Свойства ==
{{Утверждение
|about=разрешимость
|statement=
Если <tex>A\leqslant_{m}B</tex> и <tex>B</tex> разрешимо, то <tex>A</tex> разрешимо.
|proof=Пусть <tex>p</tex> — программа-разрешитель для <tex>B</tex>. Тогда для любого <tex>x\in A</tex> разрешитель должен вернуть значение <tex>p(f(x))</tex>.
}}
{{Утверждение
|about=перечислимость
|statement=
Если <tex>A\leqslant_{m}B</tex> и <tex>B</tex> перечислимо, то <tex>A</tex> перечислимо.
|proof=Аналогично предыдущему свойству.
}}
{{ТеоремаУтверждение|about=транзитивность
|statement=
Если <tex>A\le_leqslant_{m}B</tex> и <tex>B\leqslant_{m}C</tex>, то <tex>A\leqslant_{m}C</tex>.|proof=Если <tex>f:A\to B</tex> и <tex>g:B\to C</tex>, то <tex>m</tex>-сводящая функция <tex>h:A\to C</tex> выглядит так <tex>h(x) = g(f(x))</tex>.}} == Применение =={{Лемма|statement=Если <tex>A\leqslant_{m}B</tex> и <tex>A</tex> неразрешимо, то <tex>B</tex> неразрешимо.
|proof=
}}
=== Т-степени ===
Обозначим за <tex>\mathcal{D}_T</tex> множество классов эквивалентности языков по отношению <tex>\equiv_T</tex>, это множество будет множеством <tex>T</tex>-степеней (тьюринговых степеней).
{{Определение
|definition=
'''<tex>T</tex>-степенью языка <tex>L</tex>''' (англ. ''Turing degree'') называется его класс эквивалентности по отношению <tex>\equiv_T</tex>, то есть <tex>\mathrm{deg}_T(L) = \{ M \mid L \equiv_T M \}</tex>.
}}
На <tex>T</tex>-степенях можно ввести частичный порядок: для <tex>d_1, d_2 \in \mathcal{D}_T, d_1 \leqslant d_2</tex>, если для каких-то <tex>L \in d_1, M \in d_2: L \leqslant_T M</tex>, определение корректно, так как порядок не будет зависеть от выбора представителя <tex>T</tex>-степени.
==== Свойства ====
* <tex>\mathrm{R}</tex> — минимальный элемент в частичном порядке на <tex>T</tex>-степенях. Очевидно из того, что класс разрешимых языков замкнут по использованию разрешимого языка в качестве оракула.
* Любая пара <tex>T</tex>-степеней <tex>d_1, d_2 \in \mathcal{D}_T</tex> имеет наименьшую верхнюю границу <tex>d_1 \lor d_2 \in \mathcal{D}_T</tex>.
==== Тьюринговый скачок ====
Обозначим за <tex>H</tex> язык программ, останавливающихся на пустом входе. Обозначим за <tex>H^f</tex> язык программ, использующих <tex>f</tex> в качестве оракула и останавливающихся на пустом входе.
Можно показать, что:
* <tex>f <_T H^f</tex>
* Если <tex>f \leqslant_T g</tex>, то <tex>H^f \leqslant_T H^g</tex>
{{Определение
|definition=
'''Тьюринговым скачком <tex>T</tex>-степени <tex>d</tex>''' (англ. ''Turing jump'') называется <tex>T</tex>-степень языка <tex>H^L</tex>, где <tex>L</tex> — произвольный язык в <tex>d</tex>.
}}
Заметим, что если <tex>L \equiv_T M</tex>, то <tex>H^L \equiv_T H^M</tex>, поэтому определение корректно. Оператор тьюрингова скачка обозначим как <tex>J : \mathcal{D}_T \to \mathcal{D}_T</tex>.
== См. также ==
* [[Примеры неразрешимых задач: задача о выводе в полусистеме Туэ| Задача о выводе в полусистеме Туэ]]
* [[Примеры неразрешимых задач: проблема соответствий Поста | Проблема соответствий Поста]]
* [[Примеры неразрешимых задач: задача о замощении | Задача о замощении]]
* [[Неразрешимость исчисления предикатов первого порядка]]
== Источники информации ==
* [http://en.wikipedia.org/wiki/Many-one_reduction Wikipedia — Many-one reduction]
* [http://en.wikipedia.org/wiki/Turing_reduction Wikipedia — Turing reduction]
* [http://www.personal.psu.edu/t20/notes/topics-s05.pdf Topics in Logic and Foundations]
* ''Верещагин Н., Шень А.'' Вычислимые функции, 2-е изд. — МЦНМО, 2002. — С. 64. — ISBN 5-900916-36-7
* ''P. Odifreddi'' — Classical recursion theory. — Elsivier, 1992. — ISBN 0-444-87295-7
{{Заголовок со строчной буквы}}
[[Категория: Теория формальных языков]]
[[Категория: Теория вычислимости]]
[[Категория: Примеры неразрешимых задач]]
