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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Так правильнее)
Строка 18: Строка 18:
 
|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>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>, что и требовалось.
 
}}
 
}}
 
== Литература ==
 
== Литература ==

Версия 07:27, 25 декабря 2011

Определение:
Множество натуральных чисел [math]A[/math] m-сводится ко множеству натуральных чисел [math]B[/math], если существует всюду определённая вычислимая функция [math]f:\mathbb{N}\rightarrow\mathbb{N}[/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].

Свойства

  1. [math]A\le_{m}A[/math].
  2. Если [math]A\le_{m}B[/math] и [math]B[/math] разрешимо, то [math]A[/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].
  5. Если [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]B[/math] неразрешимо, то для любого разрешимого [math]X: X\ne B[/math]. Пусть мы хотим найти точку, в которой [math]X[/math] отличается от [math]B[/math]. Рассмотрим [math]f[/math] которая m-сводит [math]A[/math] к [math]B[/math]. [math]f^{-1}(X)[/math] будет разрешимым, как прообраз разрешимого множества. Поэтому можно найти точку [math]x[/math], в которой [math]X[/math] отличается от [math]A[/math]. Тогда [math]B[/math] будет отличаться от [math]X[/math] в точке [math]f(x)[/math].

Покажем, как вычислить номер [math]f^{-1}(X)[/math] по номеру [math]X[/math]. Рассмотрим множество [math]V=\{(x,y)|(x,f(y))\in W\}[/math], где [math]W[/math]главная нумерация. Оно перечислимо, поскольку является прообразом перечислимого [math]W[/math] при вычислимом отображении [math](x,y)\rightarrow(x,f(y))[/math]. [math]V_n=f^{-1}(W_n)[/math]. По свойству главной нумерации, то существует всюду определенная вычислимая функция [math]g[/math], для которой [math]\forall n:W_{g(n)}=V_n=f^{-1}(W_n)[/math], то есть [math]g[/math] даёт [math]W[/math]—номер его прообраза при отображении [math]f[/math], что и требовалось.
[math]\triangleleft[/math]

Литература

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