Материал из Викиконспекты
|
|
| Строка 13: |
Строка 13: |
| | | | |
| | | | |
| − | {{Теорема | + | {{Лемма |
| | |statement= | | |statement= |
| | Если <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= |
| − | Если <tex>B</tex> неразрешимо, то для любого разрешимого <tex>X: X\ne B</tex>. Пусть мы хотим найти точку, в которой <tex>X</tex> отличается от <tex>B</tex>. Рассмотрим <tex>f</tex> которая m-сводит <tex>A</tex> к <tex>B</tex>. <tex>f^{-1}(X)</tex> будет разрешимым, как прообраз разрешимого множества. Поэтому можно найти точку <tex>x</tex>, в которой <tex>X</tex> отличается от <tex>A</tex>. Тогда <tex>B</tex> будет отличаться от <tex>X</tex> в точке <tex>f(x)</tex>.
| + | Следует из второго свойства. Достаточно преобразовать утверждение ''Из <tex>A</tex> следует <tex>B</tex>'' к виду ''Из <tex>\overline{B}</tex> следует <tex>\overline{A}</tex>''. |
| − | | |
| − | Покажем, как вычислить номер <tex>f^{-1}(X)</tex> по номеру <tex>X</tex>. Рассмотрим множество <tex>V=\{(x,y)|(x,f(y))\in W\}</tex>, где <tex>W</tex> — [[Главные нумерации|главная нумерация]]. Оно перечислимо, поскольку является прообразом перечислимого <tex>W</tex> при вычислимом отображении <tex>(x,y)\rightarrow(x,f(y))</tex>. <tex>V_n=f^{-1}(W_n)</tex>. По свойству главной нумерации, существует всюду определенная вычислимая функция <tex>g</tex>, для которой <tex>\forall n:W_{g(n)}=V_n=f^{-1}(W_n)</tex>, то есть <tex>g</tex> даёт <tex>W</tex>—номер его прообраза при отображении <tex>f</tex>, что и требовалось.
| |
| | }} | | }} |
| | == Литература == | | == Литература == |
Версия 07:46, 18 января 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]. |
Свойства
- [math]A\le_{m}A[/math].
- Если [math]A\le_{m}B[/math] и [math]B[/math] разрешимо, то [math]A[/math] разрешимо.
- Если [math]A\le_{m}B[/math] и [math]B[/math] перечислимо, то [math]A[/math] перечислимо.
- Если [math]A\le_{m}B[/math] и [math]B\le_{m}C[/math], то [math]A\le_{m}C[/math].
- Если [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]A[/math] следует [math]B[/math] к виду Из [math]\overline{B}[/math] следует [math]\overline{A}[/math]. |
| [math]\triangleleft[/math] |
Литература
- Верещагин Н., Шень А. — Вычислимые функции, 2-е изд. МЦНМО, 2002. ISBN 5-900916-36-7
- P. Odifreddi — Classical recursion theory. Elsivier, 1992. ISBN 0-444-87295-7
