Изменения
→Сведение по Тьюрингу
{{Определение
|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\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\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>.
}}
== Применение ==
{{Лемма
|statement=
Если <tex>A\le_leqslant_{m}B</tex> и <tex>A</tex> неразрешимо, то <tex>B</tex> неразрешимо.
|proof=
Следует из второго свойства.
}}
== Литература Источники информации ==* [http://en.wikipedia.org/wiki/Many-one_reduction Wikipedia — Many-one reduction]* [http://en.wikipedia.org/wiki/Turing_reduction Wikipedia — Turing reduction]* [http://www.personal.psu.edu/t20/notes/topics-s05.pdf Topics in Logic and Foundations]* ''Верещагин Н., Шень А.'' — '''Вычислимые функции''', 2-е изд. — МЦНМО, 2002. — С. 64. — ISBN 5-900916-36-7* ''P. Odifreddi'' — '''Classical recursion theory'''. — Elsivier, 1992. — ISBN 0-444-87295-7
{{Заголовок со строчной буквы}}
[[Категория: Теория формальных языков]]
[[Категория: Теория вычислимости]]
[[Категория: Примеры неразрешимых задач]]