Изменения

|definition=Множество <tex>A</tex> '''<tex>\textbf m</tex>-сводится''' (англ. ''many-one reducible'', ''m-reducible'') ко множеству <tex>B</tex>, если существует всюду определённая [[Вычислимые функции|вычислимая функция ]] <tex>f : x\in A\Leftrightarrow f(x)\in B</tex>, то есть <tex>f(A) \subset B</tex> и <tex>f(\overline{A}) \subset \overline{B}</tex>. Обозначение: <tex>A\leqslant_{m}B</tex>.

|definition=<tex>A</tex> '''<tex>\textbf m</tex>-эквивалентно''' (англ. ''many-one equivalent'', ''m-equivalent'') <tex>B</tex>, если <tex>A\leqslant_{m}B</tex> и <tex>B\leqslant_{m}A</tex>. Обозначение: <tex>A\equiv_{m}B</tex>.

# {{Утверждение|about=рефлексивность|statement=<tex>A\leqslant_{m}A</tex>.#*'''Доказательство:''' |proof=<tex>f(x)=x</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\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>.}}

К таким задачам относятся, например, [[===Примеры применения==={{main|Примеры неразрешимых задач: проблема соответствий Поста|проблема соответствий Поста]], [[Примеры неразрешимых задач: задача о замощении|задача о замощении полимино]] и другие .}}

Язык <tex>L</tex> '''сводится по Тьюрингу''' (англ. ''Turing reducible'') к языку <tex>M</tex>, если язык <tex>ML</tex> является разрешимым с использованием <tex>LM</tex> как оракула, обозначается как <tex>L \leqslant_T M</tex>.

'''<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</tex> ''' (англ. ''Turing jump'') называется <tex>T</tex>-степень языка <tex>H^L</tex>, где <tex>L</tex> — произвольный язык в <tex>d</tex>.