M-сводимость — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Да ни у кого больше нет таких проблем с логикой, зачем это здесь?)
Строка 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\le_{m}B</tex>, то <tex>\overline{A}\le_{m}\overline{B}</tex>.
+
#*'''Доказательство:''' Если <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

Определение:
Множество [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].
    • Доказательство: [math]f(x)=x[/math].
  2. Если [math]A\le_{m}B[/math] и [math]B[/math] разрешимо, то [math]A[/math] разрешимо.
    • Доказательство: Пусть [math]p[/math] — программа-разрешитель для [math]B[/math]. Тогда для любого [math]x\in A[/math] разрешитель должен вернуть значение [math]p(f(x))[/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].
    • Доказательство: Если [math]f:A\to B[/math] и [math]g:B\to C[/math], то m-сводящая функция [math]h:A\to C[/math] выглядит так [math]h(x) = g(f(x))[/math].


Лемма:
Если [math]A\le_{m}B[/math] и [math]A[/math] неразрешимо, то [math]B[/math] неразрешимо.
Доказательство:
[math]\triangleright[/math]
Следует из второго свойства.
[math]\triangleleft[/math]

Литература

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