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

Материал из Викиконспекты
Версия от 03:05, 24 декабря 2011; Bloof (обсуждение | вклад) (Новая страница: «{{Определение |definition=Множество натуральных чисел <tex>A</tex> '''m-сводится''' ко множеству натура...»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск
Определение:
Множество натуральных чисел [math]A[/math] m-сводится ко множеству натуральных чисел [math]B[/math], если существует всюду определённая вычислимая функция [math]f:\mathbb{N}\rightarrow\mathbb{N}[/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].


Свойства

  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]B[/math] неразрешимо, то для любого разрешимого [math]X: X\ne B[/math]. Пусть мы хотим найти точку, в которой [math]X[/math] отличается от [math]B[/math]. Рассмотрим [math]f[/math] которая m-сводит [math]A[/math] к [math]B[/math]. [math]f^{-1}(X)[/math] будет разрешимым, как прообраз разрешимого множества. Поэтому можно найти точку [math]x[/math], в которой [math]X[/math] отличается от [math]A[/math]. Тогда [math]B[/math] будет отличаться от [math]X[/math] в точке [math]f(x)[/math].
[math]\triangleleft[/math]