Изменения

|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\le_leqslant_{m}A</tex>.# |proof=<tex>f(x)=x</tex>.}} {{Утверждение|about=разрешимость|statement=Если <tex>A\le_leqslant_{m}B</tex> и <tex>B</tex> разрешимо, то <tex>A</tex> разрешимо.# Если |proof=Пусть <tex>A\le_{m}Bp</tex> и — программа-разрешитель для <tex>B</tex> перечислимо, то . Тогда для любого <tex>x\in A</tex> перечислиморазрешитель должен вернуть значение <tex>p(f(x))</tex>.# }} {{Утверждение|about=перечислимость|statement=Если <tex>A\le_leqslant_{m}B</tex> и <tex>B\le_{m}C</tex>перечислимо, то <tex>A\le_{m}C</tex>перечислимо.|proof=Аналогично предыдущему свойству.# Если <tex>A\le_{m}B</tex>, то <tex>\overline{A}\le_{m}\overline{B}</tex>.

== Применение =={{ТеоремаЛемма

Если <tex>A\le_leqslant_{m}B</tex> и <tex>A</tex> неразрешимо, то <tex>B</tex> неразрешимо.

Если Следует из второго свойства. }} Приведённая лемма позволяет доказывать алгоритмическую неразрешимость некоторой задачи, сводя к ней ''(а не наоборот!)'' другую, неразрешимость которой уже доказана. ===Примеры применения==={{main|Примеры неразрешимых задач: проблема соответствий Поста|Примеры неразрешимых задач: задача о замощении}} ==Сведение по Тьюрингу=={{Определение|definition=Язык <tex>BL</tex> неразрешимо, то для любого разрешимого '''сводится по Тьюрингу''' (англ. ''Turing reducible'') к языку <tex>X: X\ne BM</tex>. Пусть мы хотим найти точку, в которой если язык <tex>XL</tex> отличается от является разрешимым с использованием <tex>BM</tex>. Рассмотрим как оракула, обозначается как <tex>fL \leqslant_T M</tex> которая m-сводит .}} {{Определение|definition=Язык <tex>AL</tex> к '''эквивалентен по Тьюрингу''' (англ. ''Turing equivalent'') языку <tex>BM</tex>. , если <tex>f^{-1}(X)L \leqslant_T M</tex> будет разрешимым, как прообраз разрешимого множества. Поэтому можно найти точку и <tex>xM \leqslant_T L</tex>, в которой обозначается как <tex>XL \equiv_T M</tex> отличается от .}} === Т-степени === Обозначим за <tex>A\mathcal{D}_T</tex>. Тогда множество классов эквивалентности языков по отношению <tex>B\equiv_T</tex> , это множество будет отличаться от множеством <tex>XT</tex> в точке <tex>f-степеней (xтьюринговых степеней)</tex>.

Покажем, как вычислить номер <tex>f^{-1}(X)</tex> по номеру <tex>X</tex>. Рассмотрим множество <tex>V=\{(x,y)Определение|(x,f(y))\in W\}definition='''</tex>, где <tex>WT</tex> — [[Главные нумерации|главная нумерация]]. Оно перечислимо, поскольку является прообразом перечислимого -степенью языка <tex>WL</tex> при вычислимом отображении <tex>''' (x,y)\rightarrow(x,f(y)англ. ''Turing degree'')называется его класс эквивалентности по отношению </tex>. <tex>V_n=f^{-1}(W_n)\equiv_T</tex>. По свойству главной нумерации, то существует всюду определенная вычислимая функция <tex>g</tex>, для которой есть <tex>\forall n:W_mathrm{gdeg}_T(nL)}=V_n=f^\{-1M \mid L \equiv_T M \}(W_n)</tex>, то есть <tex>g</tex> даёт <tex>W</tex>—номер его прообраза при отображении <tex>f</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