418
правок
Изменения
Нет описания правки
{{Определение
|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_{m}B</tex>.
}}
{{Определение
Например:
* [[Примеры неразрешимых задач: проблема соответствий Поста|неразрешимость проблемы соответствий Поста]].
==Сведение по Тьюрингу==
{{Определение
|definition=
Язык <tex>L</tex> '''сводится по Тьюрингу''' (является ''Turing reducible'') к языку <tex>M</tex>, если язык <tex>M</tex> является разрешимым с использованием <tex>L</tex> как оракула, обозначается как <tex>L \le_T M</tex>.
}}
{{Определение
|definition=Язык <tex>L</tex> '''эквивалентен по Тьюрингу''' (''Turing equivalent'') языку <tex>M</tex>, если <tex>L \le_T M</tex> и <tex>M \le_T L</tex>, обозначается как <tex>L \equiv_T M</tex>.
}}
=== Свойства ===
* рефлексивность: <tex> L \le_T L </tex>
* транзитивность: из <tex> L \le_T M </tex> и <tex> M \le_T N</tex> следует <tex> L \le_T N </tex>
== Литература ==
