Теорема Райса-Шапиро - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:31:06Z

rollbackEdits.php mass rollback

185.100.85.24 в 04:27, 1 сентября 2022

2022-09-01T04:27:26Z

84.39.244.23 в 11:54, 9 июня 2020

2020-06-09T11:54:12Z

Romanosov в 15:50, 16 января 2017

2017-01-16T15:50:15Z

Внесённые изменения

Romanosov в 22:09, 15 января 2017

2017-01-15T22:09:56Z

Romanosov в 22:09, 15 января 2017

2017-01-15T22:09:06Z

Romanosov: /* Источники информации */

2017-01-15T21:16:03Z

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

Romanosov в 21:04, 15 января 2017

2017-01-15T21:04:43Z

194.85.161.2 в 20:50, 21 января 2014

2014-01-21T20:50:02Z

Андрей Шулаев: эстетические и концептуальные правки

2013-01-20T20:00:05Z

эстетические и концептуальные правки

← Предыдущая		Версия 16:31, 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=		\|definition=

← Предыдущая		Версия 04:27, 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=		\|definition=

@@ Строка 70: / Строка 70: @@
 }}
-<tex>\Rightarrow</tex>
+<tex>\Leftarrow</tex>
 : Доказательство в одну сторону тривиально: пусть <tex>\Gamma</tex> — перечислимое множество образцов. Будем обозначать за <tex>\Gamma_i</tex> образец с номером <tex>i</tex>, а за <tex>\Gamma_{ij}</tex> — элемент с номером <tex>j</tex> образца с номером <tex>i</tex>. Далее приведён код полуразрешителя <tex>A</tex>, который принимает на вход код полуразрешителя <tex>L</tex> и возвращает значение <tex>L \in A</tex>.
@@ Строка 84: / Строка 84: @@
            '''return''' ''true''
-<tex>\Leftarrow</tex>
+<tex>\Rightarrow</tex>
 :Для доказательства в другую сторону будем использовать две леммы, приведённые выше. Полуразрешитель для множества образцов, удовлетворяющих <tex>\Gamma</tex> строится следующим образом: для каждого образца <tex>\gamma</tex> строится текст программы
    f<tex>{}_\gamma</tex>(x):

@@ Строка 29: / Строка 29: @@
 Райса-Шапиро
 |statement=
-Свойство языков <tex>A</tex> перечислимо \iff \exists\Gamma : L \in A \iff L \subseteq \Gamma .
+Свойство языков <tex>A</tex> перечислимо <tex>\iff \exists\Gamma : L \in A \iff L \subseteq \Gamma.</tex>
 }}

@@ Строка 5: / Строка 5: @@
 {{Определение
 |definition=
-'''Образцом''' (англ. ''pattern'') называется конечное множество слов, объединённое определённым общим свойством.
+'''Образцом''' (англ. ''pattern'') называется конечное множество слов, объединённое свойством.
 }}
 {{Определение
 |definition=
-'''Язык <tex>L</tex> удовлетворяет образцу <tex>A</tex>''', если <tex>L</tex> содержит все элементы <tex>A</tex>.
+'''Язык <tex>L</tex> удовлетворяет образцу <tex>X</tex>''', если <tex>L</tex> содержит все элементы <tex>X</tex>.
 }}
 {{Определение
 |definition=
-'''Язык <tex>L</tex> удовлетворяет множеству образцов <tex>X</tex>''', если <tex>L</tex> удовлетворяет хотя бы одному образцу <tex>A \in X</tex>.
+'''Язык <tex>L</tex> удовлетворяет множеству образцов <tex>\Gamma</tex>''', если <tex>L</tex> удовлетворяет хотя бы одному образцу <tex>X \in \Gamma</tex>.
 }}
 Теорема Райса-Шапиро позволяет дать простое описание перечислимым свойствам языков. Заметим, что вычислимо работать с произвольными языками возможности нет, поэтому далее неявно подразумевается, что все рассматриваемые языки являются [[Перечислимые языки|перечислимыми]].
@@ Строка 23: / Строка 29: @@
 Райса-Шапиро
 |statement=
-Свойство языков <tex>A</tex> перечислимо тогда и только тогда, когда существует перечислимое множество образцов <tex>\Gamma</tex>, такое, что <tex>L</tex> удовлетворяет <tex>A</tex> тогда и только тогда, когда <tex>L</tex> удовлетворяет <tex>\Gamma</tex>.
+Свойство языков <tex>A</tex> перечислимо \iff \exists\Gamma : L \in A \iff L \subseteq \Gamma .
 }}
@@ Строка 91: / Строка 97: @@
 == См. также==
 == Источники информации ==

← Предыдущая		Версия 21:16, 15 января 2017
Строка 95:		Строка 95:
	* ''Верещагин Н. К., Шень A.'' Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. {{---}} М.: МЦНМО, 1999. С. 134. ISBN 5-900916-36-7		* ''Верещагин Н. К., Шень A.'' Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. {{---}} М.: МЦНМО, 1999. С. 134. ISBN 5-900916-36-7
	* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. {{---}} М.: Издательский дом «Вильямс», 2008. {{---}} С. 528 {{---}} ISBN 978-5-8459-1347-0 (рус.)		* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. {{---}} М.: Издательский дом «Вильямс», 2008. {{---}} С. 528 {{---}} ISBN 978-5-8459-1347-0 (рус.)
		+
		+	[[Категория: Теория формальных языков]]
		+	[[Категория: Теория вычислимости]]
		+	[[Категория: Примеры неразрешимых задач]]

@@ Строка 1: / Строка 1: @@
 {{Определение
 |definition=
-'''Свойством программ''' называется подмножество перечислимых языков.
+'''Свойством программ''' (англ. ''property'') называется подмножество перечислимых языков.
 }}
 {{Определение
 |definition=
-'''Образцом''' называется конечное множество слов.
+'''Образцом''' (англ. ''pattern'') называется конечное множество слов, объединённое определённым общим свойством.
 }}
 {{Определение
@@ Строка 25: / Строка 25: @@
 Свойство языков <tex>A</tex> перечислимо тогда и только тогда, когда существует перечислимое множество образцов <tex>\Gamma</tex>, такое, что <tex>L</tex> удовлетворяет <tex>A</tex> тогда и только тогда, когда <tex>L</tex> удовлетворяет <tex>\Gamma</tex>.
 }}
 Доказательство в одну сторону тривиально: пусть <tex>\Gamma</tex> — перечислимое множество образцов. Будем обозначать за <tex>\Gamma_i</tex> образец с номером <tex>i</tex>, а за <tex>\Gamma_{ij}</tex> — элемент с номером <tex>j</tex> образца с номером <tex>i</tex>. Далее приведён код полуразрешителя <tex>A</tex>, который принимает на вход код полуразрешителя <tex>L</tex> и возвращает значение <tex>L \in A</tex>.
- A(L)
+  A(L):
-   '''for''' t = 1 '''to''' <tex>\infty</tex>
+    '''for''' t = 1 '''to''' <tex>\infty</tex>
-     '''for''' i = 1 '''to''' t
+      '''for''' i = 1 '''to''' t
-       ok <tex>\leftarrow</tex> true
+        ok <tex>\leftarrow</tex> true
-       '''for''' j = 1 '''to''' <tex>|\Gamma_i|</tex>
+      '''for''' j = 1 '''to''' <tex>|\Gamma_i|</tex>
-         '''if''' <tex>\lnot L|_t (\Gamma_{ij})</tex>
+        '''if''' <tex>\lnot L|_t (\Gamma_{ij})</tex>
-           ok <tex>\leftarrow</tex> false
+          ok <tex>\leftarrow</tex> false
-       '''if''' ok
+        '''if''' ok
-         '''return''' true
+          '''return''' true
 Для доказательства в другую сторону понадобятся следующие леммы:
@@ Строка 50: / Строка 55: @@
 Вычисляется эта функция следующим образом: параллельно запускаем проверки <tex>x \in G</tex> и <tex>y \in K</tex>. Если <tex>x \in G</tex>, то <tex>x \in H</tex>, следовательно, функция возвращает единицу вне зависимости от <tex>y</tex>. Если <tex>y \in K</tex>, то запускаем проверку <tex>x \in H</tex>.
-С помощью этой функции можно разрешить множество <tex>K</tex> следующим образом: для проверяемого элемента <tex>y</tex> подготовим программу <tex>g</tex>:
+Разрешим множество <tex>K</tex>с помощью этой функции. Для проверяемого элемента <tex>y</tex> подготовим программу <tex>g</tex>:
- g(x):
+  g(x):
-   '''return''' f(x, y)
+    if <tex>x \in H</tex>
 После этого запустим параллельно проверки <tex>y \in K</tex> и <tex>L(g) \in A</tex>. Если <tex>y \in K</tex>, то первая проверка завершится. Иначе функция <tex>g</tex> задаёт язык <tex>G</tex>, который обладает свойством <tex>A</tex>, следовательно, вторая проверка завершится, сигнализируя о том, что <tex>y \notin K</tex>. Но <tex>K</tex> не является разрешимым множеством, получено противоречие.
@@ Строка 67: / Строка 75: @@
 Заметим, что если <tex>y \in K</tex>, то <tex>f(x, y)</tex> распознаёт некоторое конечное подмножество <tex>G</tex> и всё множество <tex>G</tex> иначе. Эта функция тривиальным образом разрешима, построим с её помощью разрешитель <tex>K</tex>. Аналогично доказательству первой леммы, подготовим программу <tex>g</tex>:
- g(x):
+  g(x):
-   '''return''' f(x, y)
+    '''return''' f(x, y)
 После этого параллельно запустим проверки <tex>y \in K</tex> и <tex>L(g) \in A</tex>. Аналогично, данная процедура разрешает множество <tex>K</tex>. Но <tex>K</tex> не является разрешимым, получено противоречие.
 }}
 Полуразрешитель для множества образцов, удовлетворяющих <tex>\Gamma</tex> строится следующим образом: для каждого образца <tex>\gamma</tex> строится текст программы
- f<tex>{}_\gamma</tex>(x):
+  f<tex>{}_\gamma</tex>(x):
-   '''return''' x <tex>{} \in \gamma</tex>
+    '''return''' x <tex>{} \in \gamma</tex>
 Текст программы передаётся полуразрешителю <tex>A</tex>.
@@ Строка 80: / Строка 88: @@
 Пусть <tex>L \in A</tex>. Тогда по второй лемме найдётся образец <tex>\gamma</tex>, который является подмножеством <tex>L</tex> и удовлетворяет свойству <tex>A</tex>. Следовательно, этот образец лежит в множестве <tex>\Gamma</tex> и язык <tex>A</tex> удовлетворяет множеству образцов <tex>\Gamma</tex>, что и требовалось доказать.
-== Литература ==
 * ''Верещагин Н. К., Шень A.'' Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. {{---}} М.: МЦНМО, 1999. С. 134. ISBN 5-900916-36-7
 * ''Хопкрофт Д., Мотвани Р., Ульман Д.'' Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. {{---}} М.: Издательский дом «Вильямс», 2008. {{---}} С. 528 {{---}} ISBN 978-5-8459-1347-0 (рус.)