M-сводимость

Определение:

Множество [math]A[/math] m-сводится (является many-one reducible, m-reducible) ко множеству [math]B[/math], если существует всюду определённая вычислимая функция [math]f : x\in A\Leftrightarrow f(x)\in B[/math], то есть [math]f(A) \subset B[/math] и [math]f(\overline{A}) \subset \overline{B}[/math]. Обозначение: [math]A\le_{m}B[/math].

Определение:

[math]A[/math] m-эквивалентно (many-one equivalent, m-equivalent) [math]B[/math], если [math]A\le_{m}B[/math] и [math]B\le_{m}A[/math]. Обозначение: [math]A\equiv_{m}B[/math].

Свойства

1. [math]A\le_{m}A[/math].
   • Доказательство: [math]f(x)=x[/math].
2. Если [math]A\le_{m}B[/math] и [math]B[/math] разрешимо, то [math]A[/math] разрешимо.
   • Доказательство: Пусть [math]p[/math] — программа-разрешитель для [math]B[/math]. Тогда для любого [math]x\in A[/math] разрешитель должен вернуть значение [math]p(f(x))[/math].
3. Если [math]A\le_{m}B[/math] и [math]B[/math] перечислимо, то [math]A[/math] перечислимо.
   • Доказательство: Аналогично предыдущему свойству.
4. Если [math]A\le_{m}B[/math] и [math]B\le_{m}C[/math], то [math]A\le_{m}C[/math].
   • Доказательство: Если [math]f:A\to B[/math] и [math]g:B\to C[/math], то m-сводящая функция [math]h:A\to C[/math] выглядит так [math]h(x) = g(f(x))[/math].

Применение

Лемма:

Если [math]A\le_{m}B[/math] и [math]A[/math] неразрешимо, то [math]B[/math] неразрешимо.

Доказательство:

[math]\triangleright[/math]

Следует из второго свойства.

[math]\triangleleft[/math]

Приведённая лемма позволяет доказывать алгоритмическую неразрешимость некоторой задачи, сводя к ней (а не наоборот!) другую, неразрешимость которой уже доказана.

Например:

• неразрешимость проблемы соответствий Поста.

Сведение по Тьюрингу

Определение:

Язык [math]L[/math] сводится по Тьюрингу (является Turing reducible) к языку [math]M[/math], если язык [math]M[/math] является разрешимым с использованием [math]L[/math] как оракула, обозначается как [math]L \le_T M[/math].

Определение:

Язык [math]L[/math] эквивалентен по Тьюрингу (Turing equivalent) языку [math]M[/math], если [math]L \le_T M[/math] и [math]M \le_T L[/math], обозначается как [math]L \equiv_T M[/math].

Свойства

• рефлексивность: [math] L \le_T L [/math]
• транзитивность: из [math] L \le_T M [/math] и [math] M \le_T N[/math] следует [math] L \le_T N [/math]
• Очевидно, что \equiv_T --- отношение эквивалентности

Т-степени

Обозначим за \mathcal{D}_T множество классов эквивалентности языков по отношению \equiv_T, это множество будет множеством Т-степеней (тьюринговых степеней)

Определение: Т-степенью языка L называется его класс эквивалентности по отношению \equiv_T, то есть \mathrm{deg}_T(L) = \{ M \mid L \equiv_T M \}.

На Т-степенях можно ввести частичный порядок: для d_1, d_2 \in \mathcal{D}_T, d_1 \le d_2, если для каких-то L \in d_1, M \in d_2: L \le_T M, определение корректно, так как порядок не будет зависеть от выбора представителя Т-степени.

Свойства

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

Тьюринговый скачок

Обозначим за H язык программ, останавливающихся на пустом входе. Обозначим за H^f язык программ, использующих f в качестве оракула и останавливающихся на пустом входе.

Можно показать, что:

• f <_T H^f
• Если f \le_T g, то H^f \le_T H^g

Тогда тьюринговым скачком Т-степени d называется Т-степень языка H^L, где L — произвольный язык в d. Заметим, что если L \equiv_T M, то H^L \equiv_T H^M, поэтому определение корректно. Оператор тьюрингова скачка обозначим как J : \mathcal{D}_T \to \mathcal{D}_T.

Литература

• Wikipedia — Many-one reduction
• Wikipedia — Turing reduction
• Верещагин Н., Шень А. — Вычислимые функции, 2-е изд. МЦНМО, 2002, стр. 64. ISBN 5-900916-36-7
• P. Odifreddi — Classical recursion theory. Elsivier, 1992. ISBN 0-444-87295-7