Изменения

|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\le_leqslant_{m}A</tex>.#*'''Доказательство:''' |proof=<tex>f(x)=x</tex>.# }} {{Утверждение|about=разрешимость|statement=Если <tex>A\le_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\le_leqslant_{m}B</tex> и <tex>B</tex> перечислимо, то <tex>A</tex> перечислимо.#*'''Доказательство:''' |proof=Аналогично предыдущему свойству.# }} {{Утверждение|about=транзитивность|statement=Если <tex>A\le_leqslant_{m}B</tex> и <tex>B\le_leqslant_{m}C</tex>, то <tex>A\le_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>.}}

Если <tex>A\le_leqslant_{m}B</tex> и <tex>A</tex> неразрешимо, то <tex>B</tex> неразрешимо.

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

Язык <tex>L</tex> '''сводится по Тьюрингу''' (является англ. ''Turing reducible'') к языку <tex>M</tex>, если язык <tex>ML</tex> является разрешимым с использованием <tex>LM</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 L </tex>* транзитивность: из <tex> L \le_T M </tex> и <tex> M \le_T N</tex> следует <tex> L \le_T N </tex>* Очевидно, что \equiv_T --- отношение эквивалентности

{{Определение|definition== Т'''<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_1, d_2 \in \mathcal{D}_T множество классов эквивалентности языков по отношению , d_1 \equiv_Tleqslant d_2</tex>, если для каких-то <tex>L \in d_1, M \in d_2: L \leqslant_T M</tex>, определение корректно, это множество так как порядок не будет множеством Тзависеть от выбора представителя <tex>T</tex>-степеней (тьюринговых степеней)степени.

Определение: Т==== Свойства ====* <tex>\mathrm{R}</tex> — минимальный элемент в частичном порядке на <tex>T</tex>-степенью языка L называется его степенях. Очевидно из того, что класс эквивалентности разрешимых языков замкнут по отношению использованию разрешимого языка в качестве оракула.* Любая пара <tex>T</tex>-степеней <tex>d_1, d_2 \equiv_T, то есть in \mathrmmathcal{degD}_T(L) = \{ M </tex> имеет наименьшую верхнюю границу <tex>d_1 \mid L lor d_2 \equiv_T M in \mathcal{D}_T</tex>.

На Т-степенях можно ввести частичный порядок: для d_1==== Тьюринговый скачок ====Обозначим за <tex>H</tex> язык программ, d_2 \in \mathcal{D}_Tостанавливающихся на пустом входе. Обозначим за <tex>H^f</tex> язык программ, d_1 \le d_2, если для каких-то L \in d_1, M \in d_2: L \le_T M, определение корректно, так как порядок не будет зависеть от выбора представителя Т-степенииспользующих <tex>f</tex> в качестве оракула и останавливающихся на пустом входе.

=== Свойства ===* \mathrm{R} — минимальный элемент в частичном порядке на Т-степенях. Очевидно из тогоМожно показать, что класс разрешимых языков замкнут по использованию разрешимого языка в качестве оракула.* Любая пара Т-степеней d_1, d_2 \in \mathcal{D}_T имеет наименьшую верхнюю границу d_1 \lor d_2 \in \mathcal{D}_T.:

=== Тьюринговый скачок ===* <tex>f <_T H^f</tex> Обозначим за H язык программ* Если <tex>f \leqslant_T g</tex>, останавливающихся на пустом входе. Обозначим за то <tex>H^f язык программ, использующих f в качестве оракула и останавливающихся на пустом входе.\leqslant_T H^g</tex>

Можно показать{{Определение|definition= '''Тьюринговым скачком <tex>T</tex>-степени <tex>d</tex>''' (англ. ''Turing jump'') называется <tex>T</tex>-степень языка <tex>H^L</tex>, что:где <tex>L</tex> — произвольный язык в <tex>d</tex>.}}

* f Заметим, что если <_T H^f * Если f tex>L \le_T gequiv_T M</tex>, то <tex>H^f L \le_T equiv_T H^gM</tex>, поэтому определение корректно. Оператор тьюрингова скачка обозначим как <tex>J : \mathcal{D}_T \to \mathcal{D}_T</tex>.

Тогда тьюринговым скачком Т-степени d называется Т-степень языка H^L, где L — произвольный язык == См. также ==* [[Примеры неразрешимых задач: задача о выводе в полусистеме Туэ| Задача о выводе в d. Заметим, что если L \equiv_T M, то H^L \equiv_T H^M, поэтому определение корректно. Оператор тьюрингова скачка обозначим как J полусистеме Туэ]]* [[Примеры неразрешимых задач: проблема соответствий Поста | Проблема соответствий Поста]]* [[Примеры неразрешимых задач: \mathcal{D}_T \to \mathcal{D}_T.задача о замощении | Задача о замощении]]* [[Неразрешимость исчисления предикатов первого порядка]]

== Литература Источники информации ==

* [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