Изменения

|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> неразрешимо.

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

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