65
правок
Изменения
Нет описания правки
{{Определение
|definition=Множество натуральных чисел <tex>A</tex> '''m-сводится''' ко множеству натуральных чисел <tex>B</tex>, если существует всюду определённая вычислимая функция <tex>f:\mathbb{N}A\rightarrow\mathbb{N}B</tex> со свойством <tex>\forall{x}:x\in A\Leftrightarrow f(x)\in B</tex>. Обозначение: <tex>A\le_{m}B</tex>.
}}
{{Определение
Если <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>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>, что и требовалось.
}}
== Литература ==
