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]A[/math] следует [math]B[/math] к виду Из [math]\overline{B}[/math] следует [math]\overline{A}[/math].
[math]\triangleleft[/math]

Литература

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