M-сводимость
Версия от 03:05, 24 декабря 2011; Bloof (обсуждение | вклад) (Новая страница: «{{Определение |definition=Множество натуральных чисел <tex>A</tex> '''m-сводится''' ко множеству натура...»)
Определение: |
Множество натуральных чисел | m-сводится ко множеству натуральных чисел , если существует всюду определённая вычислимая функция со свойством . Обозначение: .
Определение: |
m-эквивалентно , если и . |
Свойства
- .
- Если и разрешимо, то разрешимо.
- Если и перечислимо, то перечислимо.
- Если и , то .
- Если , то .
Теорема: |
Если и неразрешимо, то неразрешимо. |
Доказательство: |
Если | неразрешимо, то для любого разрешимого . Пусть мы хотим найти точку, в которой отличается от . Рассмотрим которая m-сводит к . будет разрешимым, как прообраз разрешимого множества. Поэтому можно найти точку , в которой отличается от . Тогда будет отличаться от в точке .