M-сводимость — различия между версиями
Kirelagin (обсуждение | вклад) (Да ни у кого больше нет таких проблем с логикой, зачем это здесь?) |
Bloof (обсуждение | вклад) |
||
Строка 7: | Строка 7: | ||
== Свойства == | == Свойства == | ||
# <tex>A\le_{m}A</tex>. | # <tex>A\le_{m}A</tex>. | ||
+ | #*'''Доказательство:''' <tex>f(x)=x</tex>. | ||
# Если <tex>A\le_{m}B</tex> и <tex>B</tex> разрешимо, то <tex>A</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</tex> перечислимо, то <tex>A</tex> перечислимо. | ||
+ | #*'''Доказательство:''' Аналогично предыдущему свойству. | ||
# Если <tex>A\le_{m}B</tex> и <tex>B\le_{m}C</tex>, то <tex>A\le_{m}C</tex>. | # Если <tex>A\le_{m}B</tex> и <tex>B\le_{m}C</tex>, то <tex>A\le_{m}C</tex>. | ||
− | # Если <tex>A\ | + | #*'''Доказательство:''' Если <tex>f:A\to B</tex> и <tex>g:B\to C</tex>, то m-сводящая функция <tex>h:A\to C</tex> выглядит так <tex>h(x) = g(f(x))</tex>. |
Строка 17: | Строка 20: | ||
Если <tex>A\le_{m}B</tex> и <tex>A</tex> неразрешимо, то <tex>B</tex> неразрешимо. | Если <tex>A\le_{m}B</tex> и <tex>A</tex> неразрешимо, то <tex>B</tex> неразрешимо. | ||
|proof= | |proof= | ||
− | Следует из второго свойства. | + | Следует из второго свойства. |
}} | }} | ||
== Литература == | == Литература == |
Версия 03:34, 19 января 2012
Определение: |
Множество | m-сводится ко множеству , если существует всюду определённая вычислимая функция со свойством . Обозначение: .
Определение: |
m-эквивалентно , если и . Обозначение: . |
Свойства
-
- Доказательство: .
.
- Если
- Доказательство: Пусть — программа-разрешитель для . Тогда для любого разрешитель должен вернуть значение .
и разрешимо, то разрешимо.
- Если
- Доказательство: Аналогично предыдущему свойству.
и перечислимо, то перечислимо.
- Если
- Доказательство: Если и , то m-сводящая функция выглядит так .
и , то .
Лемма: |
Если и неразрешимо, то неразрешимо. |
Доказательство: |
Следует из второго свойства. |
Литература
- Верещагин Н., Шень А. — Вычислимые функции, 2-е изд. МЦНМО, 2002. ISBN 5-900916-36-7
- P. Odifreddi — Classical recursion theory. Elsivier, 1992. ISBN 0-444-87295-7