65
правок
Изменения
Нет описания правки
== Свойства ==
# <tex>A\le_{m}A</tex>.
#*'''Доказательство:''' <tex>f(x)=x</tex>.
# Если <tex>A\le_{m}B</tex> и <tex>B</tex> разрешимо, то <tex>A</tex> разрешимо.
#*'''Доказательство:''' Пусть <tex>p</tex> — программа-разрешитель для <tex>B</tex>. Тогда для любого <tex>x\in A</tex> разрешитель должен вернуть значение <tex>p(f(x))</tex>.
# Если <tex>A\le_{m}B</tex> и <tex>B</tex> перечислимо, то <tex>A</tex> перечислимо.
#*'''Доказательство:''' Аналогично предыдущему свойству.
# Если <tex>A\le_{m}B</tex> и <tex>B\le_{m}C</tex>, то <tex>A\le_{m}C</tex>.
# *'''Доказательство:''' Если <tex>f:A\le_{m}to B</tex> и <tex>g:B\to C</tex>, то m-сводящая функция <tex>\overline{h:A}\le_{m}\overline{B}to C</tex> выглядит так <tex>h(x) = g(f(x))</tex>.
Если <tex>A\le_{m}B</tex> и <tex>A</tex> неразрешимо, то <tex>B</tex> неразрешимо.
|proof=
Следует из второго свойства.
}}
== Литература ==
