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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показана 31 промежуточная версия 6 участников)
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
|definition=Множество <tex>A</tex> '''m-сводится''' (является ''many-one reducible'', ''m-reducible'') ко множеству <tex>B</tex>, если существует всюду определённая вычислимая функция <tex>f : x\in A\Leftrightarrow f(x)\in B</tex>, то есть <tex>f(A) \subset B</tex> и <tex>f(\overline{A}) \subset \overline{B}</tex>. Обозначение: <tex>A\le_{m}B</tex>.
+
|definition=Множество <tex>A</tex> '''<tex>\textbf m</tex>-сводится''' (англ. ''many-one reducible'', ''m-reducible'') ко множеству <tex>B</tex>, если существует всюду определённая [[Вычислимые функции|вычислимая функция]] <tex>f : x\in A\Leftrightarrow f(x)\in B</tex>, то есть <tex>f(A) \subset B</tex> и <tex>f(\overline{A}) \subset \overline{B}</tex>. Обозначение: <tex>A\leqslant_{m}B</tex>.
 
}}
 
}}
 
{{Определение
 
{{Определение
|definition=<tex>A</tex> '''m-эквивалентно''' (''many-one equivalent'', ''m-equivalent'') <tex>B</tex>, если <tex>A\le_{m}B</tex> и <tex>B\le_{m}A</tex>. Обозначение: <tex>A\equiv_{m}B</tex>.
+
|definition=<tex>A</tex> '''<tex>\textbf m</tex>-эквивалентно''' (англ. ''many-one equivalent'', ''m-equivalent'') <tex>B</tex>, если <tex>A\leqslant_{m}B</tex> и <tex>B\leqslant_{m}A</tex>. Обозначение: <tex>A\equiv_{m}B</tex>.
 
}}
 
}}
 
== Свойства ==
 
== Свойства ==
# <tex>A\le_{m}A</tex>.
+
{{Утверждение
#*'''Доказательство:''' <tex>f(x)=x</tex>.
+
|about=рефлексивность
# Если <tex>A\le_{m}B</tex> и <tex>B</tex> разрешимо, то <tex>A</tex> разрешимо.
+
|statement=
#*'''Доказательство:''' Пусть <tex>p</tex> — программа-разрешитель для <tex>B</tex>. Тогда для любого <tex>x\in A</tex> разрешитель должен вернуть значение <tex>p(f(x))</tex>.
+
<tex>A\leqslant_{m}A</tex>.
# Если <tex>A\le_{m}B</tex> и <tex>B</tex> перечислимо, то <tex>A</tex> перечислимо.
+
|proof=<tex>f(x)=x</tex>.
#*'''Доказательство:''' Аналогично предыдущему свойству.
+
}}
# Если <tex>A\le_{m}B</tex> и <tex>B\le_{m}C</tex>, то <tex>A\le_{m}C</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>.
+
{{Утверждение
 +
|about=разрешимость
 +
|statement=
 +
Если <tex>A\leqslant_{m}B</tex> и <tex>B</tex> разрешимо, то <tex>A</tex> разрешимо.
 +
|proof=Пусть <tex>p</tex> — программа-разрешитель для <tex>B</tex>. Тогда для любого <tex>x\in A</tex> разрешитель должен вернуть значение <tex>p(f(x))</tex>.
 +
}}
 +
 +
{{Утверждение
 +
|about=перечислимость
 +
|statement=
 +
Если <tex>A\leqslant_{m}B</tex> и <tex>B</tex> перечислимо, то <tex>A</tex> перечислимо.
 +
|proof=Аналогично предыдущему свойству.
 +
}}
 +
 
 +
{{Утверждение
 +
|about=транзитивность
 +
|statement=
 +
Если <tex>A\leqslant_{m}B</tex> и <tex>B\leqslant_{m}C</tex>, то <tex>A\leqslant_{m}C</tex>.
 +
|proof=Если <tex>f:A\to B</tex> и <tex>g:B\to C</tex>, то <tex>m</tex>-сводящая функция <tex>h:A\to C</tex> выглядит так <tex>h(x) = g(f(x))</tex>.
 +
}}
  
 
== Применение ==
 
== Применение ==
 
{{Лемма
 
{{Лемма
 
|statement=
 
|statement=
Если <tex>A\le_{m}B</tex> и <tex>A</tex> неразрешимо, то <tex>B</tex> неразрешимо.
+
Если <tex>A\leqslant_{m}B</tex> и <tex>A</tex> неразрешимо, то <tex>B</tex> неразрешимо.
 
|proof=
 
|proof=
 
Следует из второго свойства.  
 
Следует из второго свойства.  
Строка 25: Строка 44:
 
Приведённая лемма позволяет доказывать алгоритмическую неразрешимость некоторой задачи, сводя к ней ''(а не наоборот!)'' другую, неразрешимость которой уже доказана.
 
Приведённая лемма позволяет доказывать алгоритмическую неразрешимость некоторой задачи, сводя к ней ''(а не наоборот!)'' другую, неразрешимость которой уже доказана.
  
Например:
+
===Примеры применения===
* [[Примеры неразрешимых задач: проблема соответствий Поста|неразрешимость проблемы соответствий Поста]].
+
{{main|Примеры неразрешимых задач: проблема соответствий Поста|Примеры неразрешимых задач: задача о замощении}}
  
 
==Сведение по Тьюрингу==
 
==Сведение по Тьюрингу==
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Язык <tex>L</tex> '''сводится по Тьюрингу''' (является ''Turing reducible'') к языку <tex>M</tex>, если язык <tex>M</tex> является разрешимым с использованием <tex>L</tex> как оракула, обозначается как <tex>L \le_T M</tex>.
+
Язык <tex>L</tex> '''сводится по Тьюрингу''' (англ. ''Turing reducible'') к языку <tex>M</tex>, если язык <tex>L</tex> является разрешимым с использованием <tex>M</tex> как оракула, обозначается как <tex>L \leqslant_T M</tex>.
 
}}
 
}}
  
 
{{Определение
 
{{Определение
|definition=Язык <tex>L</tex> '''эквивалентен по Тьюрингу''' (''Turing equivalent'') языку <tex>M</tex>, если <tex>L \le_T M</tex> и <tex>M \le_T L</tex>, обозначается как <tex>L \equiv_T M</tex>.
+
|definition=Язык <tex>L</tex> '''эквивалентен по Тьюрингу''' (англ. ''Turing equivalent'') языку <tex>M</tex>, если <tex>L \leqslant_T M</tex> и <tex>M \leqslant_T L</tex>, обозначается как <tex>L \equiv_T M</tex>.
 
}}
 
}}
 
=== Свойства ===
 
* рефлексивность: <tex> L \le_T L </tex>
 
* транзитивность: из <tex> L \le_T M </tex> и <tex> M \le_T N</tex> следует <tex> L \le_T N </tex>
 
* Очевидно, что <tex>\equiv_T</tex> — отношение эквивалентности
 
 
  
 
=== Т-степени ===
 
=== Т-степени ===
  
Обозначим за <tex>\mathcal{D}_T</tex> множество классов эквивалентности языков по отношению <tex>\equiv_T</tex>, это множество будет множеством Т-степеней (тьюринговых степеней).
+
Обозначим за <tex>\mathcal{D}_T</tex> множество классов эквивалентности языков по отношению <tex>\equiv_T</tex>, это множество будет множеством <tex>T</tex>-степеней (тьюринговых степеней).
  
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Т-степенью языка <tex>L</tex> называется его класс эквивалентности по отношению <tex>\equiv_T</tex>, то есть <tex>\mathrm{deg}_T(L) = \{ M \mid L \equiv_T M \}</tex>.
+
'''<tex>T</tex>-степенью языка <tex>L</tex>''' (англ. ''Turing degree'') называется его класс эквивалентности по отношению <tex>\equiv_T</tex>, то есть <tex>\mathrm{deg}_T(L) = \{ M \mid L \equiv_T M \}</tex>.
 
}}
 
}}
  
На Т-степенях можно ввести частичный порядок: для <tex>d_1, d_2 \in \mathcal{D}_T, d_1 \le d_2</tex>, если для каких-то <tex>L \in d_1, M \in d_2: L \le_T M</tex>, определение корректно, так как порядок не будет зависеть от выбора представителя Т-степени.
+
На <tex>T</tex>-степенях можно ввести частичный порядок: для <tex>d_1, d_2 \in \mathcal{D}_T, d_1 \leqslant d_2</tex>, если для каких-то <tex>L \in d_1, M \in d_2: L \leqslant_T M</tex>, определение корректно, так как порядок не будет зависеть от выбора представителя <tex>T</tex>-степени.
  
 
==== Свойства ====
 
==== Свойства ====
* <tex>\mathrm{R}</tex> — минимальный элемент в частичном порядке на Т-степенях. Очевидно из того, что класс разрешимых языков замкнут по использованию разрешимого языка в качестве оракула.
+
* <tex>\mathrm{R}</tex> — минимальный элемент в частичном порядке на <tex>T</tex>-степенях. Очевидно из того, что класс разрешимых языков замкнут по использованию разрешимого языка в качестве оракула.
* Любая пара Т-степеней <tex>d_1, d_2 \in \mathcal{D}_T</tex> имеет наименьшую верхнюю границу <tex>d_1 \lor d_2 \in \mathcal{D}_T</tex>.
+
* Любая пара <tex>T</tex>-степеней <tex>d_1, d_2 \in \mathcal{D}_T</tex> имеет наименьшую верхнюю границу <tex>d_1 \lor d_2 \in \mathcal{D}_T</tex>.
  
 
==== Тьюринговый скачок ====
 
==== Тьюринговый скачок ====
Строка 65: Строка 78:
  
 
* <tex>f <_T H^f</tex>  
 
* <tex>f <_T H^f</tex>  
* Если <tex>f \le_T g</tex>, то <tex>H^f \le_T H^g</tex>
+
* Если <tex>f \leqslant_T g</tex>, то <tex>H^f \leqslant_T H^g</tex>
 +
 
 +
{{Определение
 +
|definition=
 +
'''Тьюринговым скачком <tex>T</tex>-степени <tex>d</tex>''' (англ. ''Turing jump'') называется <tex>T</tex>-степень языка <tex>H^L</tex>, где <tex>L</tex> — произвольный язык в <tex>d</tex>.
 +
}}
 +
 
 +
Заметим, что если <tex>L \equiv_T M</tex>, то <tex>H^L \equiv_T H^M</tex>, поэтому определение корректно. Оператор тьюрингова скачка обозначим как <tex>J : \mathcal{D}_T \to \mathcal{D}_T</tex>.
  
Тогда тьюринговым скачком Т-степени <tex>d</tex> называется Т-степень языка <tex>H^L</tex>, где <tex>L</tex> — произвольный язык в <tex>d</tex>. Заметим, что если <tex>L \equiv_T M</tex>, то <tex>H^L \equiv_T H^M</tex>, поэтому определение корректно. Оператор тьюрингова скачка обозначим как <tex>J : \mathcal{D}_T \to \mathcal{D}_T</tex>.
+
== См. также ==
 +
* [[Примеры неразрешимых задач: задача о выводе в полусистеме Туэ| Задача о выводе в полусистеме Туэ]]
 +
* [[Примеры неразрешимых задач: проблема соответствий Поста | Проблема соответствий Поста]]
 +
* [[Примеры неразрешимых задач: задача о замощении | Задача о замощении]]
 +
* [[Неразрешимость исчисления предикатов первого порядка]]
  
== Литература ==
+
== Источники информации ==
 
* [http://en.wikipedia.org/wiki/Many-one_reduction Wikipedia — Many-one reduction]
 
* [http://en.wikipedia.org/wiki/Many-one_reduction Wikipedia — Many-one reduction]
 
* [http://en.wikipedia.org/wiki/Turing_reduction Wikipedia — Turing reduction]
 
* [http://en.wikipedia.org/wiki/Turing_reduction Wikipedia — Turing reduction]
* ''Верещагин Н., Шень А.'' — '''Вычислимые функции''', 2-е изд. МЦНМО, 2002, стр. 64. ISBN 5-900916-36-7
+
* [http://www.personal.psu.edu/t20/notes/topics-s05.pdf Topics in Logic and Foundations]
* ''P. Odifreddi'' — '''Classical recursion theory'''. Elsivier, 1992. ISBN 0-444-87295-7
+
* ''Верещагин Н., Шень А.'' Вычислимые функции, 2-е изд. МЦНМО, 2002. — С. 64. ISBN 5-900916-36-7
 +
* ''P. Odifreddi'' — Classical recursion theory. Elsivier, 1992. ISBN 0-444-87295-7
 
{{Заголовок со строчной буквы}}
 
{{Заголовок со строчной буквы}}
 +
 +
[[Категория: Теория формальных языков]]
 +
[[Категория: Теория вычислимости]]
 +
[[Категория: Примеры неразрешимых задач]]

Текущая версия на 19:15, 4 сентября 2022

Определение:
Множество [math]A[/math] [math]\textbf m[/math]-сводится (англ. many-one reducible, m-reducible) ко множеству [math]B[/math], если существует всюду определённая вычислимая функция [math]f : x\in A\Leftrightarrow f(x)\in B[/math], то есть [math]f(A) \subset B[/math] и [math]f(\overline{A}) \subset \overline{B}[/math]. Обозначение: [math]A\leqslant_{m}B[/math].


Определение:
[math]A[/math] [math]\textbf m[/math]-эквивалентно (англ. many-one equivalent, m-equivalent) [math]B[/math], если [math]A\leqslant_{m}B[/math] и [math]B\leqslant_{m}A[/math]. Обозначение: [math]A\equiv_{m}B[/math].

Свойства

Утверждение (рефлексивность):
[math]A\leqslant_{m}A[/math].
[math]\triangleright[/math]
[math]f(x)=x[/math].
[math]\triangleleft[/math]
Утверждение (разрешимость):
Если [math]A\leqslant_{m}B[/math] и [math]B[/math] разрешимо, то [math]A[/math] разрешимо.
[math]\triangleright[/math]
Пусть [math]p[/math] — программа-разрешитель для [math]B[/math]. Тогда для любого [math]x\in A[/math] разрешитель должен вернуть значение [math]p(f(x))[/math].
[math]\triangleleft[/math]
Утверждение (перечислимость):
Если [math]A\leqslant_{m}B[/math] и [math]B[/math] перечислимо, то [math]A[/math] перечислимо.
[math]\triangleright[/math]
Аналогично предыдущему свойству.
[math]\triangleleft[/math]
Утверждение (транзитивность):
Если [math]A\leqslant_{m}B[/math] и [math]B\leqslant_{m}C[/math], то [math]A\leqslant_{m}C[/math].
[math]\triangleright[/math]
Если [math]f:A\to B[/math] и [math]g:B\to C[/math], то [math]m[/math]-сводящая функция [math]h:A\to C[/math] выглядит так [math]h(x) = g(f(x))[/math].
[math]\triangleleft[/math]

Применение

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

Приведённая лемма позволяет доказывать алгоритмическую неразрешимость некоторой задачи, сводя к ней (а не наоборот!) другую, неразрешимость которой уже доказана.

Примеры применения

Сведение по Тьюрингу

Определение:
Язык [math]L[/math] сводится по Тьюрингу (англ. Turing reducible) к языку [math]M[/math], если язык [math]L[/math] является разрешимым с использованием [math]M[/math] как оракула, обозначается как [math]L \leqslant_T M[/math].


Определение:
Язык [math]L[/math] эквивалентен по Тьюрингу (англ. Turing equivalent) языку [math]M[/math], если [math]L \leqslant_T M[/math] и [math]M \leqslant_T L[/math], обозначается как [math]L \equiv_T M[/math].


Т-степени

Обозначим за [math]\mathcal{D}_T[/math] множество классов эквивалентности языков по отношению [math]\equiv_T[/math], это множество будет множеством [math]T[/math]-степеней (тьюринговых степеней).


Определение:
[math]T[/math]-степенью языка [math]L[/math] (англ. Turing degree) называется его класс эквивалентности по отношению [math]\equiv_T[/math], то есть [math]\mathrm{deg}_T(L) = \{ M \mid L \equiv_T M \}[/math].


На [math]T[/math]-степенях можно ввести частичный порядок: для [math]d_1, d_2 \in \mathcal{D}_T, d_1 \leqslant d_2[/math], если для каких-то [math]L \in d_1, M \in d_2: L \leqslant_T M[/math], определение корректно, так как порядок не будет зависеть от выбора представителя [math]T[/math]-степени.

Свойства

  • [math]\mathrm{R}[/math] — минимальный элемент в частичном порядке на [math]T[/math]-степенях. Очевидно из того, что класс разрешимых языков замкнут по использованию разрешимого языка в качестве оракула.
  • Любая пара [math]T[/math]-степеней [math]d_1, d_2 \in \mathcal{D}_T[/math] имеет наименьшую верхнюю границу [math]d_1 \lor d_2 \in \mathcal{D}_T[/math].

Тьюринговый скачок

Обозначим за [math]H[/math] язык программ, останавливающихся на пустом входе. Обозначим за [math]H^f[/math] язык программ, использующих [math]f[/math] в качестве оракула и останавливающихся на пустом входе.

Можно показать, что:

  • [math]f \lt _T H^f[/math]
  • Если [math]f \leqslant_T g[/math], то [math]H^f \leqslant_T H^g[/math]


Определение:
Тьюринговым скачком [math]T[/math]-степени [math]d[/math] (англ. Turing jump) называется [math]T[/math]-степень языка [math]H^L[/math], где [math]L[/math] — произвольный язык в [math]d[/math].


Заметим, что если [math]L \equiv_T M[/math], то [math]H^L \equiv_T H^M[/math], поэтому определение корректно. Оператор тьюрингова скачка обозначим как [math]J : \mathcal{D}_T \to \mathcal{D}_T[/math].

См. также

Источники информации