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

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

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

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

[math]A[/math] m-эквивалентно [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].
2. Если [math]A\le_{m}B[/math] и [math]B[/math] разрешимо, то [math]A[/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].
5. Если [math]A\le_{m}B[/math], то [math]\overline{A}\le_{m}\overline{B}[/math].

Лемма:

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

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

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

Литература

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