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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Сведение по Тьюрингу)
Строка 1: Строка 1:
 +
{| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
 +
|+
 +
|-align="center"
 +
|'''НЕТ ВОЙНЕ'''
 +
|-style="font-size: 16px;"
 +
|
 +
24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
 +
 +
Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
 +
 +
Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
 +
 +
Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
 +
 +
''Антивоенный комитет России''
 +
|-style="font-size: 16px;"
 +
|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
 +
|-style="font-size: 16px;"
 +
|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
 +
|}
 +
 
{{Определение
 
{{Определение
 
|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> '''<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>.

Версия 08:52, 1 сентября 2022

НЕТ ВОЙНЕ

24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.

Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.

Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.

Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.

Антивоенный комитет России

Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки.


Определение:
Множество [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].

См. также

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