M-сводимость - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:15:08Z

rollbackEdits.php mass rollback

185.220.102.8 в 05:52, 1 сентября 2022

2022-09-01T05:52:34Z

94.45.202.56: /* Сведение по Тьюрингу */

2017-12-19T22:53:49Z

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

Ateuhh: /* Отношение эквивалентности */

2016-12-16T08:26:43Z

‎Отношение эквивалентности

Ateuhh в 16:26, 12 декабря 2016

2016-12-12T16:26:57Z

Ateuhh: /* Отношение эквивалентности */

2016-12-12T16:15:01Z

‎Отношение эквивалентности

Ateuhh: /* Отношение эквивалентности */

2016-12-12T16:13:45Z

‎Отношение эквивалентности

Ateuhh: /* Отношение эквивалентности */

2016-12-12T09:21:09Z

‎Отношение эквивалентности

Ateuhh в 08:46, 12 декабря 2016

2016-12-12T08:46:27Z

Ateuhh: /* Т-степени */

2016-12-12T08:37:46Z

‎Т-степени

← Предыдущая		Версия 16:15, 4 сентября 2022
Строка 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>.

← Предыдущая		Версия 05:52, 1 сентября 2022
Строка 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>.

@@ Строка 50: / Строка 50: @@
 {{Определение
 |definition=
-Язык <tex>L</tex> '''сводится по Тьюрингу''' (англ. ''Turing reducible'') к языку <tex>M</tex>, если язык <tex>M</tex> является разрешимым с использованием <tex>L</tex> как оракула, обозначается как <tex>L \leqslant_T M</tex>.
+Язык <tex>L</tex> '''сводится по Тьюрингу''' (англ. ''Turing reducible'') к языку <tex>M</tex>, если язык <tex>L</tex> является разрешимым с использованием <tex>M</tex> как оракула, обозначается как <tex>L \leqslant_T M</tex>.
 }}

@@ Строка 5: / Строка 5: @@
 |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>.
 }}
-== Отношение эквивалентности ==
+== Свойства ==
 {{Утверждение
 |about=рефлексивность
@@ Строка 32: / Строка 32: @@
 Если <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>.
 }}

@@ Строка 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\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>.
 }}
 {{Определение
-|definition=<tex>A</tex> '''m-эквивалентно''' (англ. ''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>.
+|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>.
 }}
 == Отношение эквивалентности ==

@@ Строка 31: / Строка 31: @@
 |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>, то m-сводящая функция <tex>h:A\to C</tex> выглядит так <tex>h(x) = g(f(x))</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>.
 }}

@@ Строка 38: / Строка 38: @@
 |statement=
 Отношение сводимости является отношением эквивалентности
-|proof= Следует из рефлексивности, разрешимости и транзитивности.
+|proof= Следует из рефлексивности, симметричности и транзитивности.
 }}

← Предыдущая		Версия 08:46, 12 декабря 2016
Строка 91:		Строка 91:

	Заметим, что если <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>L \equiv_T M</tex>, то <tex>H^L \equiv_T H^M</tex>, поэтому определение корректно. Оператор тьюрингова скачка обозначим как <tex>J : \mathcal{D}_T \to \mathcal{D}_T</tex>.
		+
		+	== См. также ==
		+	* [[Примеры неразрешимых задач: задача о выводе в полусистеме Туэ\| Задача о выводе в полусистеме Туэ]]
		+	* [[Примеры неразрешимых задач: проблема соответствий Поста \| Проблема соответствий Поста]]
		+	* [[Примеры неразрешимых задач: задача о замощении \| Задача о замощении]]
		+	* [[Неразрешимость исчисления предикатов первого порядка]]

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

@@ Строка 87: / Строка 87: @@
 {{Определение
 |definition=
-  '''Тьюринговым скачком <tex>T</tex>-степени <tex>d</tex>''' называется <tex>T</tex>-степень языка <tex>H^L</tex>, где <tex>L</tex> — произвольный язык в <tex>d</tex>.
+  '''Тьюринговым скачком <tex>T</tex>-степени <tex>d</tex>''' (англ. ''Turing jump'') называется <tex>T</tex>-степень языка <tex>H^L</tex>, где <tex>L</tex> — произвольный язык в <tex>d</tex>.
 }}