Изменения
→Сведение по Тьюрингу
{{Определение
|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}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>.
}}
== Применение ==
{{Лемма
{{Определение
|definition=
Язык <tex>L</tex> '''сводится по Тьюрингу''' (англ. ''Turing reducible'') к языку <tex>M</tex>, если язык <tex>ML</tex> является разрешимым с использованием <tex>LM</tex> как оракула, обозначается как <tex>L \leqslant_T M</tex>.
}}
