Изменения
Нет описания правки
{{Определение
|definition=Множество <tex>A</tex> '''m-сводится''' (является ''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\le_leqslant_{m}B</tex>.
}}
{{Определение
|definition=<tex>A</tex> '''m-эквивалентно''' (''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>.
}}
== Свойства ==
# <tex>A\le_leqslant_{m}A</tex>.
#*'''Доказательство:''' <tex>f(x)=x</tex>.
# Если <tex>A\le_leqslant_{m}B</tex> и <tex>B</tex> разрешимо, то <tex>A</tex> разрешимо.
#*'''Доказательство:''' Пусть <tex>p</tex> — программа-разрешитель для <tex>B</tex>. Тогда для любого <tex>x\in A</tex> разрешитель должен вернуть значение <tex>p(f(x))</tex>.
# Если <tex>A\le_leqslant_{m}B</tex> и <tex>B</tex> перечислимо, то <tex>A</tex> перечислимо.
#*'''Доказательство:''' Аналогично предыдущему свойству.
# Если <tex>A\le_leqslant_{m}B</tex> и <tex>B\le_leqslant_{m}C</tex>, то <tex>A\le_leqslant_{m}C</tex>.
#*'''Доказательство:''' Если <tex>f:A\to B</tex> и <tex>g:B\to C</tex>, то m-сводящая функция <tex>h:A\to C</tex> выглядит так <tex>h(x) = g(f(x))</tex>.
{{Лемма
|statement=
Если <tex>A\le_leqslant_{m}B</tex> и <tex>A</tex> неразрешимо, то <tex>B</tex> неразрешимо.
|proof=
Следует из второго свойства.
{{Определение
|definition=
Язык <tex>L</tex> '''сводится по Тьюрингу''' (является ''Turing reducible'') к языку <tex>M</tex>, если язык <tex>M</tex> является разрешимым с использованием <tex>L</tex> как оракула, обозначается как <tex>L \le_T leqslant_T M</tex>.
}}
{{Определение
|definition=Язык <tex>L</tex> '''эквивалентен по Тьюрингу''' (''Turing equivalent'') языку <tex>M</tex>, если <tex>L \le_T leqslant_T M</tex> и <tex>M \le_T leqslant_T L</tex>, обозначается как <tex>L \equiv_T M</tex>.
}}
=== Свойства ===
* рефлексивность: <tex> L \le_T leqslant_T L </tex>* транзитивность: из <tex> L \le_T leqslant_T M </tex> и <tex> M \le_T leqslant_T N</tex> следует <tex> L \le_T leqslant_T N </tex>
* Очевидно, что <tex>\equiv_T</tex> — отношение эквивалентности
}}
На Т-степенях можно ввести частичный порядок: для <tex>d_1, d_2 \in \mathcal{D}_T, d_1 \le d_2</tex>, если для каких-то <tex>L \in d_1, M \in d_2: L \le_T leqslant_T M</tex>, определение корректно, так как порядок не будет зависеть от выбора представителя Т-степени.
==== Свойства ====
