Викиконспекты - Вклад участника [ru]

Обсуждение:Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций

2011-12-20T23:06:10Z

Roman Livarsky:

=== ToDo ===
«РазрешАтель». Ты серьёзно? 
Разрешимые языки, <tex>L_{1}^*</tex>: во-первых, мы должны посмотреть не на одно разбиение, а на все возможные (кстати, как написано в описании, но не в коде), во-вторых, там в коде бред написан. 
Разрешимые языки, <tex>L_1 L_2</tex>: в коде тоже не перебираются разбиения. 
Не понятно, зачем в полуразрешителе для пересечения тайм-лимиты. 
То же самое для полуразрешителя для <tex>L_1 \times L_2</tex>. 
Для языка <tex>L_{1}^*</tex> по аналогии с разрешимостью. Разбиения не перебираются. Ну и тоже бред в коде. Ну и в описании тоже бред: какой тайм-лимит, если его нет?? 
Что за бред вообще с последней программой? Говорится про перечислитель, написан полуразрешитель. 
А ещё меня глобально не устраивают эти фигурные скобки в каждой теореме. [[Участник:Leugenea|Евгений Лукьянец]]

Возможно исправил.
[[Участник:Roman Livarsky|Рома]]

=== ToDo2 ===
Полуразрешители для объединения, замыкания Клини и конкатенации языков неверные. 
Волевым решением я считаю, что надо приводить либо полуразрешитель, либо перечислитель, потому что мы умеем делать из одного другое. 
В конце: «Тогда имея какое-либо слово» {{---}} продолбана запятая. 
«…мы знаем, что существуют перечислимые, но не разрешимые языки…» {{---}} сделать ссылку на соответствующий факт. [[Участник:Leugenea|Евгений Лукьянец]]

Исправил полуразрешитель для объединения. Для всех языков оставил только полуразрешитель. Сделал ссылку. [[Участник:Roman Livarsky|Рома]]

Исправил полуразрешитель для Клини и конкатенации. [[Участник:Roman Livarsky|Рома]]

Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций

2011-12-20T22:53:28Z

Roman Livarsky:

{{Теорема
|statement=
Языки <tex> L_1, L_2 </tex> {{---}} разрешимы, тогда следующие языки разрешимы:

* Объединение <tex>L_1</tex> и <tex>L_2\ (L_1 \cup L_2)</tex>
* Пересечение <tex>L_1</tex> и <tex>L_2\ (L_1 \cap L_2)</tex>
* Дополнение <tex>L_1\ (\overline{L_1})</tex>
* Разность <tex>L_1</tex> и <tex>L_2\ (L_1 \backslash L_2)</tex>
* Декартово произведение <tex>L_1</tex> и <tex>L_2\ (L_1 \times L_2)</tex>
* Замыкание Клини <tex>L_1\ (L_1^*)</tex>
* Конкатенация <tex>L_1</tex> и <tex>L_2\ (L_1 L_2)</tex>

|proof=
Пусть <tex>p_1</tex> и <tex>p_2</tex> {{---}} разрешающие программы для языков
<tex>L_1</tex> и <tex>L_2</tex> соответственно. Для доказательства достаточно написать разрешающую программу (разрешитель) для каждого случая.

* Разрешающая программа для языка <tex> L_1 \cup L_2 :</tex>

<tex>p(x)</tex>
'''return''' <tex>(p_1(x) == 1) \lor (p_2(x) == 1)</tex>

* Для языка <tex> L_1 \cap L_2 :</tex>

<tex>p(x)</tex>
'''return''' <tex>(p_1(x) == 1) \land (p_2(x) == 1)</tex>

* Для языка <tex> \overline{L_1} :</tex>

<tex>p(x)</tex>
'''return''' <tex>(p_1(x) == 0)</tex>

* Для языка <tex> L_1 \backslash L_2 :</tex>

<tex>p(x)</tex>
'''return''' <tex>(p_1(x) == 1) \land (p_2(x) == 0)</tex>

* Для языка <tex> L_1 \times L_2 :</tex>

<tex>p(\langle x, y \rangle)</tex>
'''return''' <tex>(p_1(x) == 1) \land (p_2(y) == 1)</tex>

* Для языка <tex>L_1^* :</tex>

<tex>p(x)</tex>
'''forall''' <tex>{\{x_i\}}_{i=1}^n \in P </tex>, где <tex>P</tex> {{---}} множество всех возможных разбиений слова <tex>x</tex> на подстроки
'''if''' <tex>(p_1(x_1) == 1) \land (p_1(x_2) == 1) \land \ ... \ \land (p_1(x_n) == 1)</tex>
'''return''' 1
'''return''' 0

Разрешитель будет перебирать все возможные разбиения данного ему слова на подстроки и для каждой проверять принадлежность <tex> L_1 </tex>. Если хотя бы в одном разбиении все подстроки будут принадлежать <tex> L_1 </tex>, то все слово принадлежит <tex> L_1^* </tex>, иначе {{---}} не принадлежит.

* Для языка <tex> L_1 L_2 : </tex>

<tex>p(x)</tex>
'''forall''' <tex>{\{x_i\}}_{i=1}^2 \in P </tex>, где <tex>P</tex> {{---}} множество всех возможных разбиений слова <tex>x</tex> на две подстроки
'''if''' <tex>(p_1(x_1) == 1) \land (p_2(x_2) == 1)</tex>
'''return''' 1
'''return''' 0

Разрешитель будет перебирать все возможные разбиения на два слова и проверять принадлежность первого слова <tex> L_1 </tex> и второго слова <tex> L_2 </tex>. Если хотя бы для одного разбиения оба разрешителя вернут 1, то слово принадлежит <tex> L_1 L_2 </tex>, иначе {{---}} не принадлежит.
}}

{{Теорема
|statement=
Языки <tex> L_1, L_2 </tex> {{---}} перечислимы, тогда следующие языки перечислимы:

* Объединение <tex>L_1</tex> и <tex>L_2\ (L_1 \cup L_2)</tex>
* Пересечение <tex>L_1</tex> и <tex>L_2\ (L_1 \cap L_2)</tex>
* Декартово произведение <tex>L_1</tex> и <tex>L_2\ (L_1 \times L_2)</tex>
* Замыкание Клини <tex>L_1\ (L_1^*)</tex>
* Конкатенация <tex>L_1</tex> и <tex>L_2\ (L_1 L_2)</tex>

|proof=

Пусть <tex>p_1</tex> и <tex>p_2</tex> {{---}} полуразрешающие программы для языков <tex>L_1</tex> и <tex>L_2</tex> соответственно. Для доказательства достаточно написать полуразрешающую программу для каждого случая. Заметим, что <tex>p_1</tex> и <tex>p_2</tex> могут зависнуть при использовании в полуразрешающей программе для соответствующего языка, но это допустимо.

* Полуразрешающая программа для языка <tex> L_1 \cup L_2 :</tex>

<tex>p(x)</tex>
'''for''' <tex>k = 1 \ .. \ \infty</tex>
'''if''' <tex> (p_1(x)|_k == 1) \lor (p_2(x)|_k == 1) </tex>
'''return 1'''

* Для языка <tex> L_1 \cap L_2 :</tex>

<tex>p(x)</tex>
'''if''' <tex> (p_1(x) == 1) \land (p_2(x) == 1) </tex>
'''return 1'''

* Для языка <tex> L_1 \times L_2 :</tex>

<tex>p(\langle x, y \rangle)</tex>
'''if''' <tex> (p_1(x) == 1) \land (p_2(y) == 1) </tex>
'''return 1'''

* Для языка <tex> L_1^* :</tex>

<tex>p(x)</tex>
'''for''' <tex>k = 1 \ .. \ \infty</tex>
'''forall''' <tex>{\{x_i\}}_{i=1}^n \in P </tex>, где <tex>P</tex> {{---}} множество всех возможных разбиений слова <tex>x</tex> на подстроки
'''if''' <tex>(p_1|_k(x_1) == 1) \land (p_1|_k(x_2) == 1) \land \ ... \ \land (p_1|_k(x_n) == 1)</tex>
'''return 1'''

* Для языка <tex> L_1 L_2 : </tex>

<tex>p(x)</tex>
'''for''' <tex>k = 1 \ .. \ \infty</tex>
'''forall''' <tex>{\{x_i\}}_{i=1}^2 \in P </tex>, где <tex>P</tex> {{---}} множество всех возможных разбиений слова <tex>x</tex> на две подстроки
'''if''' <tex>(p_1|_k(x_1) == 1) \land (p_2|_k(x_2) == 1)</tex>
'''return 1'''
 
}}

{{Теорема
|statement=
Языки <tex> L_1, L_2 </tex> {{---}} перечислимы, тогда следующие языки могут быть не перечислимы:

* Дополнение <tex>L_1\ (\overline{L_1})</tex>
* Разность <tex>L_1</tex> и <tex>L_2\ (L_1 \backslash L_2)</tex>

|proof=

Рассмотрим язык <tex> \overline{L_1} </tex>. Предположим, что он перечислим. Тогда, имея какое-либо слово, мы можем одновременно запустить перечислители для <tex> L_1 </tex> и <tex> \overline{L_1} </tex>. В какой-то момент времени слово появится либо в выводе перечислителя для <tex> L_1 </tex>, либо в выводе перечислителя для <tex> \overline{L_1} </tex>. Тогда получится что <tex> L_1 </tex> разрешим, так как про любое слово мы можем узнать принадлежит оно <tex> L_1 </tex> или не принадлежит. Но мы знаем, что [[Разрешимые (рекурсивные) языки#Пример неразрешимого множества|существуют перечислимые, но не разрешимые языки]], следовательно, язык <tex> \overline{L_1} </tex> может быть не перечислим.

Теперь рассмотрим <tex> L_1 \backslash L_2 </tex>. В качестве <tex> L_1 </tex> возьмем язык, состоящий из всех слов. Тогда получится, что язык <tex> L_1 \backslash L_2 </tex> это <tex> \overline{L_2} </tex>. Про язык <tex> \overline{L_2} </tex> мы знаем, что он перечислим не всегда, следовательно и язык <tex> L_1 \backslash L_2 </tex> также не всегда перечислим.
}}

== Литература ==
* ''Верещагин Н. К., Шень А.'' '''Лекции по математической логике и теории алгоритов. Часть 3. Вычислимые функции''' {{---}} М.: МЦНМО, 1999

Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций

2011-12-20T22:34:36Z

Roman Livarsky:

{{Теорема
|statement=
Языки <tex> L_1, L_2 </tex> {{---}} разрешимы, тогда следующие языки разрешимы:

* Объединение <tex>L_1</tex> и <tex>L_2\ (L_1 \cup L_2)</tex>
* Пересечение <tex>L_1</tex> и <tex>L_2\ (L_1 \cap L_2)</tex>
* Дополнение <tex>L_1\ (\overline{L_1})</tex>
* Разность <tex>L_1</tex> и <tex>L_2\ (L_1 \backslash L_2)</tex>
* Декартово произведение <tex>L_1</tex> и <tex>L_2\ (L_1 \times L_2)</tex>
* Замыкание Клини <tex>L_1\ (L_1^*)</tex>
* Конкатенация <tex>L_1</tex> и <tex>L_2\ (L_1 L_2)</tex>

|proof=
Пусть <tex>p_1</tex> и <tex>p_2</tex> {{---}} разрешающие программы для языков
<tex>L_1</tex> и <tex>L_2</tex> соответственно. Для доказательства достаточно написать разрешающую программу (разрешитель) для каждого случая.

* Разрешающая программа для языка <tex> L_1 \cup L_2 :</tex>

<tex>p(x)</tex>
'''return''' <tex>(p_1(x) == 1) \lor (p_2(x) == 1)</tex>

* Для языка <tex> L_1 \cap L_2 :</tex>

<tex>p(x)</tex>
'''return''' <tex>(p_1(x) == 1) \land (p_2(x) == 1)</tex>

* Для языка <tex> \overline{L_1} :</tex>

<tex>p(x)</tex>
'''return''' <tex>(p_1(x) == 0)</tex>

* Для языка <tex> L_1 \backslash L_2 :</tex>

<tex>p(x)</tex>
'''return''' <tex>(p_1(x) == 1) \land (p_2(x) == 0)</tex>

* Для языка <tex> L_1 \times L_2 :</tex>

<tex>p(\langle x, y \rangle)</tex>
'''return''' <tex>(p_1(x) == 1) \land (p_2(y) == 1)</tex>

* Для языка <tex>L_1^* :</tex>

<tex>p(x)</tex>
'''forall''' <tex>{\{x_i\}}_{i=1}^n \in P </tex>, где <tex>P</tex> {{---}} множество всех возможных разбиений слова <tex>x</tex> на подстроки
'''if''' <tex>(p_1(x_1) == 1) \land (p_1(x_2) == 1) \land \ ... \ \land (p_1(x_n) == 1)</tex>
'''return''' 1
'''return''' 0

Разрешитель будет перебирать все возможные разбиения данного ему слова на подстроки, и для каждой проверять принадлежность <tex> L_1 </tex>. Если хотя бы в одном разбиении все подстроки будут принадлежать <tex> L_1 </tex>, то все слово принадлежит <tex> L_1^* </tex>, иначе {{---}} не принадлежит.

* Для языка <tex> L_1 L_2 : </tex>

<tex>p(x)</tex>
'''forall''' <tex>{\{x_i\}}_{i=1}^2 \in P </tex>, где <tex>P</tex> {{---}} множество всех возможных разбиений слова <tex>x</tex> на две подстроки
'''if''' <tex>(p_1(x_1) == 1) \land (p_2(x_2) == 1)</tex>
'''return''' 1
'''return''' 0

Разрешитель будет перебирать все возможные разбиения на два слова и проверять принадлежность первого слова <tex> L_1 </tex> и второго слова <tex> L_2 </tex>. Если хотя бы для одного разбиения оба разрешителя вернут 1, то слово принадлежит <tex> L_1 L_2 </tex>, иначе {{---}} не принадлежит.
}}

{{Теорема
|statement=
Языки <tex> L_1, L_2 </tex> {{---}} перечислимы, тогда следующие языки перечислимы:

* Объединение <tex>L_1</tex> и <tex>L_2\ (L_1 \cup L_2)</tex>
* Пересечение <tex>L_1</tex> и <tex>L_2\ (L_1 \cap L_2)</tex>
* Декартово произведение <tex>L_1</tex> и <tex>L_2\ (L_1 \times L_2)</tex>
* Замыкание Клини <tex>L_1\ (L_1^*)</tex>
* Конкатенация <tex>L_1</tex> и <tex>L_2\ (L_1 L_2)</tex>

|proof=

Пусть <tex>p_1</tex> и <tex>p_2</tex> {{---}} полуразрешающие программы для языков <tex>L_1</tex> и <tex>L_2</tex> соответственно. Для доказательства достаточно написать полуразрешающую программу для каждого случая. Заметим, что <tex>p_1</tex> и <tex>p_2</tex> могут зависнуть при использовании в полуразрешающей программе для соответствующего языка, но это допустимо.

* Полуразрешающая программа для языка <tex> L_1 \cup L_2 :</tex>

<tex>p(x)</tex>
'''for''' <tex>k = 1 \ .. \ \infty</tex>
'''if''' <tex> (p_1(x)|_k == 1) \lor (p_2(x)|_k == 1) </tex>
'''return 1'''

* Для языка <tex> L_1 \cap L_2 :</tex>

<tex>p(x)</tex>
'''if''' <tex> (p_1(x) == 1) \land (p_2(x) == 1) </tex>
'''return 1'''

* Для языка <tex> L_1 \times L_2 :</tex>

<tex>p(\langle x, y \rangle)</tex>
'''if''' <tex> (p_1(x) == 1) \land (p_2(y) == 1) </tex>
'''return 1'''

* Для языка <tex> L_1^* :</tex>

<tex>p(x)</tex>
'''for''' <tex>k = 1 \ .. \ \infty</tex>
'''forall''' <tex>{\{x_i\}}_{i=1}^n \in P </tex>, где <tex>P</tex> {{---}} множество всех возможных разбиений слова <tex>x</tex> на подстроки
'''if''' <tex>(p_1|_k(x_1) == 1) \land (p_1|_k(x_2) == 1) \land \ ... \ \land (p_1|_k(x_n) == 1)</tex>
'''return 1'''

* Для языка <tex> L_1 L_2 : </tex>

<tex>p(x)</tex>
'''for''' <tex>k = 1 \ .. \ \infty</tex>
'''forall''' <tex>{\{x_i\}}_{i=1}^2 \in P </tex>, где <tex>P</tex> {{---}} множество всех возможных разбиений слова <tex>x</tex> на две подстроки
'''if''' <tex>(p_1|_k(x_1) == 1) \land (p_2|_k(x_2) == 1)</tex>
'''return 1'''
 
}}

{{Теорема
|statement=
Языки <tex> L_1, L_2 </tex> {{---}} перечислимы, тогда следующие языки могут быть не перечислимы:

* Дополнение <tex>L_1\ (\overline{L_1})</tex>
* Разность <tex>L_1</tex> и <tex>L_2\ (L_1 \backslash L_2)</tex>

|proof=

Рассмотрим язык <tex> \overline{L_1} </tex>. Предположим, что он перечислим. Тогда, имея какое-либо слово, мы можем одновременно запустить перечислители для <tex> L_1 </tex> и <tex> \overline{L_1} </tex>. В какой-то момент времени слово появится либо в выводе перечислителя для <tex> L_1 </tex>, либо в выводе перечислителя для <tex> \overline{L_1} </tex>. Тогда получится что <tex> L_1 </tex> разрешим, так как про любое слово мы можем узнать принадлежит оно <tex> L_1 </tex> или не принадлежит. Но мы знаем, что [[Разрешимые (рекурсивные) языки#Пример неразрешимого множества|существуют перечислимые, но не разрешимые языки]], следовательно, язык <tex> \overline{L_1} </tex> может быть не перечислим.

Теперь рассмотрим <tex> L_1 \backslash L_2 </tex>. В качестве <tex> L_1 </tex> возьмем язык, состоящий из всех слов. Тогда получится, что язык <tex> L_1 \backslash L_2 </tex> это <tex> \overline{L_2} </tex>. Про язык <tex> \overline{L_2} </tex> мы знаем, что он перечислим не всегда, следовательно и язык <tex> L_1 \backslash L_2 </tex> также не всегда перечислим.
}}

== Литература ==
* ''Верещагин Н. К., Шень А.'' '''Лекции по математической логике и теории алгоритов. Часть 3. Вычислимые функции''' {{---}} М.: МЦНМО, 1999

Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций

2011-12-20T10:07:28Z

Roman Livarsky:

{{Теорема
|statement=
Языки <tex> L_1, L_2 </tex> {{---}} разрешимы, тогда следующие языки разрешимы:

* Объединение <tex>L_1</tex> и <tex>L_2\ (L_1 \cup L_2)</tex>
* Пересечение <tex>L_1</tex> и <tex>L_2\ (L_1 \cap L_2)</tex>
* Дополнение <tex>L_1\ (\overline{L_1})</tex>
* Разность <tex>L_1</tex> и <tex>L_2\ (L_1 \backslash L_2)</tex>
* Декартово произведение <tex>L_1</tex> и <tex>L_2\ (L_1 \times L_2)</tex>
* Замыкание Клини <tex>L_1\ (L_1^*)</tex>
* Конкатенация <tex>L_1</tex> и <tex>L_2\ (L_1 L_2)</tex>

|proof=
Пусть <tex>p_1</tex> и <tex>p_2</tex> {{---}} разрешающие программы для языков
<tex>L_1</tex> и <tex>L_2</tex> соответственно. Для доказательства достаточно написать разрешающую программу (разрешитель) для каждого случая.

* Разрешающая программа для языка <tex> L_1 \cup L_2 :</tex>

<tex>p(x)</tex>
'''return''' <tex>(p_1(x) == 1) \lor (p_2(x) == 1)</tex>

* Для языка <tex> L_1 \cap L_2 :</tex>

<tex>p(x)</tex>
'''return''' <tex>(p_1(x) == 1) \land (p_2(x) == 1)</tex>

* Для языка <tex> \overline{L_1} :</tex>

<tex>p(x)</tex>
'''return''' <tex>(p_1(x) == 0)</tex>

* Для языка <tex> L_1 \backslash L_2 :</tex>

<tex>p(x)</tex>
'''return''' <tex>(p_1(x) == 1) \land (p_2(x) == 0)</tex>

* Для языка <tex> L_1 \times L_2 :</tex>

<tex>p(\langle x, y \rangle)</tex>
'''return''' <tex>(p_1(x) == 1) \land (p_2(y) == 1)</tex>

* Для языка <tex>L_1^* :</tex>

<tex>p(x)</tex>
'''forall''' <tex>x_1x_2 \ .. \ x_n :</tex> все возможные разбиения <tex>x</tex>
'''if''' <tex>(p_1(x_1) == 1) \land (p_1(x_2) == 1) \land \ ... \ \land (p_1(x_n) == 1)</tex>
'''return''' 1
'''return''' 0

Разрешитель будет перебирать все возможные разбиения данного ему слова на подслова, и для каждого проверять принадлежность <tex> L_1 </tex>. Если хотя бы в одном разбиении все подслова будут принадлежать <tex> L_1 </tex>, то все слово принадлежит <tex> L_1^* </tex>, иначе {{---}} не принадлежит.

* Для языка <tex> L_1 L_2 : </tex>

<tex>p(x)</tex>
'''forall''' <tex>x_1x_2 :</tex> все возможные разбиения <tex>x</tex> на две части
'''if''' <tex>(p_1(x_1) == 1 \land p_2(x_2) == 1)</tex>
'''return''' 1
'''return''' 0

Разрешитель будет перебирать все возможные разбиения на два слова и проверять принадлежность первого слова <tex> L_1 </tex> и второго слова <tex> L_2 </tex>. Если хотя бы для одного разбиения оба разрешителя вернут 1, то слово принадлежит <tex> L_1 L_2 </tex>, иначе {{---}} не принадлежит.
}}

{{Теорема
|statement=
Языки <tex> L_1, L_2 </tex> {{---}} перечислимы, тогда следующие языки перечислимы:

* Объединение <tex>L_1</tex> и <tex>L_2\ (L_1 \cup L_2)</tex>
* Пересечение <tex>L_1</tex> и <tex>L_2\ (L_1 \cap L_2)</tex>
* Декартово произведение <tex>L_1</tex> и <tex>L_2\ (L_1 \times L_2)</tex>
* Замыкание Клини <tex>L_1\ (L_1^*)</tex>
* Конкатенация <tex>L_1</tex> и <tex>L_2\ (L_1 L_2)</tex>

|proof=

Пусть <tex>p_1</tex> и <tex>p_2</tex> {{---}} полуразрешающие программы для языков <tex>L_1</tex> и <tex>L_2</tex> соответственно. Для доказательства достаточно написать полуразрешающую программу для каждого случая. Заметим, что <tex>p_1</tex> и <tex>p_2</tex> могут зависнуть при использовании в полуразрешающей программе для соответствующего языка, но это допустимо.

* Полуразрешающая программа для языка <tex> L_1 \cup L_2 :</tex>

<tex>p(x)</tex>
'''for''' <tex>k = 1 \ .. \ \infty</tex>
'''if''' <tex> (p_1(x)|_k == 1) \lor (p_2(x)|_k == 1) </tex>
'''return 1'''

* Для языка <tex> L_1 \cap L_2 :</tex>

<tex>p(x)</tex>
'''if''' <tex> (p_1(x) == 1) \land (p_2(x) == 1) </tex>
'''return 1'''

* Для языка <tex> L_1 \times L_2 :</tex>

<tex>p(\langle x, y \rangle)</tex>
'''if''' <tex> (p_1(x) == 1) \land (p_2(y) == 1) </tex>
'''return 1'''

* Для языка <tex> L_1^* :</tex>

<tex>p(x)</tex>
'''forall''' <tex>x_1x_2 \ .. \ x_n :</tex> все возможные разбиения <tex>x</tex>
'''if''' <tex>(p_1(x_1) == 1) \land (p_1(x_2) == 1) \land \ ... \ \land (p_1(x_n) == 1)</tex>
'''return 1'''

* Для языка <tex> L_1 L_2 : </tex>

<tex>p(x)</tex>
'''forall''' <tex>x_1x_2 :</tex> все возможные разбиения <tex>x</tex> на две части
'''if''' <tex>(p_1(x_1) == 1 \land p_2(x_2) == 1)</tex>
'''return 1'''
 
}}

{{Теорема
|statement=
Языки <tex> L_1, L_2 </tex> {{---}} перечислимы, тогда следующие языки могут быть не перечислимы:

* Дополнение <tex>L_1\ (\overline{L_1})</tex>
* Разность <tex>L_1</tex> и <tex>L_2\ (L_1 \backslash L_2)</tex>

|proof=

Рассмотрим язык <tex> \overline{L_1} </tex>. Предположим, что он перечислим. Тогда, имея какое-либо слово, мы можем одновременно запустить перечислители для <tex> L_1 </tex> и <tex> \overline{L_1} </tex>. В какой-то момент времени слово появится либо в выводе перечислителя для <tex> L_1 </tex>, либо в выводе перечислителя для <tex> \overline{L_1} </tex>. Тогда получится что <tex> L_1 </tex> разрешим, так как про любое слово мы можем узнать принадлежит оно <tex> L_1 </tex> или не принадлежит. Но мы знаем, что [[Разрешимые (рекурсивные) языки#Пример неразрешимого множества|существуют перечислимые, но не разрешимые языки]], следовательно, язык <tex> \overline{L_1} </tex> может быть не перечислим.

Теперь рассмотрим <tex> L_1 \backslash L_2 </tex>. В качестве <tex> L_1 </tex> возьмем язык, состоящий из всех слов. Тогда получится, что язык <tex> L_1 \backslash L_2 </tex> это <tex> \overline{L_2} </tex>. Про язык <tex> \overline{L_2} </tex> мы знаем, что он перечислим не всегда, следовательно и язык <tex> L_1 \backslash L_2 </tex> также не всегда перечислим.
}}

== Литература ==
* ''Верещагин Н. К., Шень А.'' '''Лекции по математической логике и теории алгоритов. Часть 3. Вычислимые функции''' {{---}} М.: МЦНМО, 1999

Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций

2011-12-20T07:16:36Z

Roman Livarsky:

{{Теорема
|statement=
Языки <tex> L_1, L_2 </tex> {{---}} разрешимы, тогда следующие языки разрешимы:

* Объединение <tex>L_1</tex> и <tex>L_2\ (L_1 \cup L_2)</tex>
* Пересечение <tex>L_1</tex> и <tex>L_2\ (L_1 \cap L_2)</tex>
* Дополнение <tex>L_1\ (\overline{L_1})</tex>
* Разность <tex>L_1</tex> и <tex>L_2\ (L_1 \backslash L_2)</tex>
* Декартово произведение <tex>L_1</tex> и <tex>L_2\ (L_1 \times L_2)</tex>
* Замыкание Клини <tex>L_1\ (L_1^*)</tex>
* Конкатенация <tex>L_1</tex> и <tex>L_2\ (L_1 L_2)</tex>

|proof=
Пусть <tex>p_1</tex> и <tex>p_2</tex> {{---}} разрешающие программы для языков
<tex>L_1</tex> и <tex>L_2</tex> соответственно. Для доказательства достаточно написать разрешающую программу (разрешитель) для каждого случая.

* Разрешающая программа для языка <tex> L_1 \cup L_2 :</tex>

<tex>p(x)</tex>
'''return''' <tex>(p_1(x) == 1) \lor (p_2(x) == 1)</tex>

* Для языка <tex> L_1 \cap L_2 :</tex>

<tex>p(x)</tex>
'''return''' <tex>(p_1(x) == 1) \land (p_2(x) == 1)</tex>

* Для языка <tex> \overline{L_1} :</tex>

<tex>p(x)</tex>
'''return''' <tex>(p_1(x) == 0)</tex>

* Для языка <tex> L_1 \backslash L_2 :</tex>

<tex>p(x)</tex>
'''return''' <tex>(p_1(x) == 1) \land (p_2(x) == 0)</tex>

* Для языка <tex> L_1 \times L_2 :</tex>

<tex>p(\langle x, y \rangle)</tex>
'''return''' <tex>(p_1(x) == 1) \land (p_2(y) == 1)</tex>

* Для языка <tex>L_1^* :</tex>

<tex>p(x)</tex>
'''forall''' <tex>x_{d_1}x_{d_2} \ .. \ x_{d_n} :</tex> все возможные разбиения <tex>x</tex>
'''if''' <tex>(p_1(x_{d_1}) == 1) \land (p_1(x_{d_2}) == 1) \land \ ... \ \land (p_1(x_{d_n}) == 1)</tex>
'''return''' 1
'''return''' 0

Разрешитель будет перебирать все возможные разбиения данного ему слова на подслова, и для каждого проверять принадлежность <tex> L_1 </tex>. Если хотя бы в одном разбиении все подслова будут принадлежать <tex> L_1 </tex>, то все слово принадлежит <tex> L_1^* </tex>, иначе {{---}} не принадлежит.

* Для языка <tex> L_1 L_2 : </tex>

<tex>p(x)</tex>
'''forall''' <tex>x_{d_1}x_{d_2} :</tex> все возможные разбиения <tex>x</tex> на две части
'''if''' <tex>(p_1(x_{d_1}) == 1 \land p_2(x_{d_2}) == 1)</tex>
'''return''' 1
'''return''' 0

Разрешитель будет перебирать все возможные разбиения на два слова и проверять принадлежность первого слова <tex> L_1 </tex> и второго слова <tex> L_2 </tex>. Если хотя бы для одного разбиения оба разрешителя вернут 1, то слово принадлежит <tex> L_1 L_2 </tex>, иначе {{---}} не принадлежит.
}}

{{Теорема
|statement=
Языки <tex> L_1, L_2 </tex> {{---}} перечислимы, тогда следующие языки перечислимы:

* Объединение <tex>L_1</tex> и <tex>L_2\ (L_1 \cup L_2)</tex>
* Пересечение <tex>L_1</tex> и <tex>L_2\ (L_1 \cap L_2)</tex>
* Декартово произведение <tex>L_1</tex> и <tex>L_2\ (L_1 \times L_2)</tex>
* Замыкание Клини <tex>L_1\ (L_1^*)</tex>
* Конкатенация <tex>L_1</tex> и <tex>L_2\ (L_1 L_2)</tex>

|proof=

Пусть <tex>p_1</tex> и <tex>p_2</tex> {{---}} полуразрешающие программы для языков <tex>L_1</tex> и <tex>L_2</tex> соответственно. Для доказательства достаточно написать полуразрешающую программу для каждого случая. Заметим, что <tex>p_1</tex> и <tex>p_2</tex> могут зависнуть при использовании в полуразрешающей программе для соответствующего языка, но это допустимо.

* Полуразрешающая программа для языка <tex> L_1 \cup L_2 :</tex>

<tex>p(x)</tex>
'''for''' <tex>k = 1 \ .. \ \infty</tex>
'''if''' <tex> (p_1(x)|_k == 1) \lor (p_2(x)|_k == 1) </tex>
'''return 1'''

* Для языка <tex> L_1 \cap L_2 :</tex>

<tex>p(x)</tex>
'''if''' <tex> (p_1(x) == 1) \land (p_2(x) == 1) </tex>
'''return 1'''

* Для языка <tex> L_1 \times L_2 :</tex>

<tex>p(\langle x, y \rangle)</tex>
'''if''' <tex> (p_1(x) == 1) \land (p_2(y) == 1) </tex>
'''return 1'''

* Для языка <tex> L_1^* :</tex>

<tex>p(x)</tex>
'''forall''' <tex>x_{d_1}x_{d_2} \ .. \ x_{d_n} :</tex> все возможные разбиения <tex>x</tex>
'''if''' <tex>(p_1(x_{d_1}) == 1) \land (p_1(x_{d_2}) == 1) \land \ ... \ \land (p_1(x_{d_n}) == 1)</tex>
'''return 1'''

* Для языка <tex> L_1 L_2 : </tex>

<tex>p(x)</tex>
'''forall''' <tex>x_{d_1}x_{d_2} :</tex> все возможные разбиения <tex>x</tex> на две части
'''if''' <tex>(p_1(x_{d_1}) == 1 \land p_2(x_{d_2}) == 1)</tex>
'''return 1'''
 
}}

{{Теорема
|statement=
Языки <tex> L_1, L_2 </tex> {{---}} перечислимы, тогда следующие языки могут быть не перечислимы:

* Дополнение <tex>L_1\ (\overline{L_1})</tex>
* Разность <tex>L_1</tex> и <tex>L_2\ (L_1 \backslash L_2)</tex>

|proof=

Рассмотрим язык <tex> \overline{L_1} </tex>. Предположим, что он перечислим. Тогда, имея какое-либо слово, мы можем одновременно запустить перечислители для <tex> L_1 </tex> и <tex> \overline{L_1} </tex>. В какой-то момент времени слово появится либо в выводе перечислителя для <tex> L_1 </tex>, либо в выводе перечислителя для <tex> \overline{L_1} </tex>. Тогда получится что <tex> L_1 </tex> разрешим, так как про любое слово мы можем узнать принадлежит оно <tex> L_1 </tex> или не принадлежит. Но мы знаем, что [[Разрешимые (рекурсивные) языки#Пример неразрешимого множества|существуют перечислимые, но не разрешимые языки]], следовательно, язык <tex> \overline{L_1} </tex> может быть не перечислим.

Теперь рассмотрим <tex> L_1 \backslash L_2 </tex>. В качестве <tex> L_1 </tex> возьмем язык, состоящий из всех слов. Тогда получится, что язык <tex> L_1 \backslash L_2 </tex> это <tex> \overline{L_2} </tex>. Про язык <tex> \overline{L_2} </tex> мы знаем, что он перечислим не всегда, следовательно и язык <tex> L_1 \backslash L_2 </tex> также не всегда перечислим.
}}

== Литература ==
* ''Верещагин Н. К., Шень А.'' '''Лекции по математической логике и теории алгоритов. Часть 3. Вычислимые функции''' {{---}} М.: МЦНМО, 1999

Обсуждение:Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций

2011-12-20T07:03:28Z

Roman Livarsky:

=== ToDo ===
«РазрешАтель». Ты серьёзно? 
Разрешимые языки, <tex>L_{1}^*</tex>: во-первых, мы должны посмотреть не на одно разбиение, а на все возможные (кстати, как написано в описании, но не в коде), во-вторых, там в коде бред написан. 
Разрешимые языки, <tex>L_1 L_2</tex>: в коде тоже не перебираются разбиения. 
Не понятно, зачем в полуразрешителе для пересечения тайм-лимиты. 
То же самое для полуразрешителя для <tex>L_1 \times L_2</tex>. 
Для языка <tex>L_{1}^*</tex> по аналогии с разрешимостью. Разбиения не перебираются. Ну и тоже бред в коде. Ну и в описании тоже бред: какой тайм-лимит, если его нет?? 
Что за бред вообще с последней программой? Говорится про перечислитель, написан полуразрешитель. 
А ещё меня глобально не устраивают эти фигурные скобки в каждой теореме. [[Участник:Leugenea|Евгений Лукьянец]]

Возможно исправил.
[[Участник:Roman Livarsky|Рома]]

=== ToDo2 ===
Полуразрешители для объединения, замыкания Клини и конкатенации языков неверные. 
Волевым решением я считаю, что надо приводить либо полуразрешитель, либо перечислитель, потому что мы умеем делать из одного другое. 
В конце: «Тогда имея какое-либо слово» {{---}} продолбана запятая. 
«…мы знаем, что существуют перечислимые, но не разрешимые языки…» {{---}} сделать ссылку на соответствующий факт. [[Участник:Leugenea|Евгений Лукьянец]]

Исправил полуразрешитель для объединения. Изменил для Клини и конкатенации. Для всех языков оставил только полуразрешитель. Сделал ссылку. [[Участник:Roman Livarsky|Рома]]

Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций

2011-12-20T06:58:02Z

Roman Livarsky:

{{Теорема
|statement=
Языки <tex> L_1, L_2 </tex> {{---}} разрешимы, тогда следующие языки разрешимы:

* Объединение <tex>L_1</tex> и <tex>L_2\ (L_1 \cup L_2)</tex>
* Пересечение <tex>L_1</tex> и <tex>L_2\ (L_1 \cap L_2)</tex>
* Дополнение <tex>L_1\ (\overline{L_1})</tex>
* Разность <tex>L_1</tex> и <tex>L_2\ (L_1 \backslash L_2)</tex>
* Декартово произведение <tex>L_1</tex> и <tex>L_2\ (L_1 \times L_2)</tex>
* Замыкание Клини <tex>L_1\ (L_1^*)</tex>
* Конкатенация <tex>L_1</tex> и <tex>L_2\ (L_1 L_2)</tex>

|proof=
Пусть <tex>p_1</tex> и <tex>p_2</tex> {{---}} разрешающие программы для языков
<tex>L_1</tex> и <tex>L_2</tex> соответственно. Для доказательства достаточно написать разрешающую программу (разрешитель) для каждого случая.

* Разрешающая программа для языка <tex> L_1 \cup L_2 :</tex>

<tex>p(x)</tex>
'''return''' <tex>(p_1(x) == 1) \lor (p_2(x) == 1)</tex>

* Для языка <tex> L_1 \cap L_2 :</tex>

<tex>p(x)</tex>
'''return''' <tex>(p_1(x) == 1) \land (p_2(x) == 1)</tex>

* Для языка <tex> \overline{L_1} :</tex>

<tex>p(x)</tex>
'''return''' <tex>(p_1(x) == 0)</tex>

* Для языка <tex> L_1 \backslash L_2 :</tex>

<tex>p(x)</tex>
'''return''' <tex>(p_1(x) == 1) \land (p_2(x) == 0)</tex>

* Для языка <tex> L_1 \times L_2 :</tex>

<tex>p(\langle x, y \rangle)</tex>
'''return''' <tex>(p_1(x) == 1) \land (p_2(y) == 1)</tex>

* Для языка <tex>L_1^* :</tex>

<tex>p(x)</tex>
'''forall''' <tex>d_i :</tex> все возможные разбиения
<tex>x_{d_1}x_{d_2} \ .. \ x_{d_n} :</tex> текущее разбиение <tex>x</tex>
'''if''' <tex>(p_1(x_{d_1}) == 1) \land (p_1(x_{d_2}) == 1) \land \ ... \ \land (p_1(x_{d_n}) == 1)</tex>
'''return''' 1
'''return''' 0

Разрешитель будет перебирать все возможные разбиения данного ему слова на подслова, и для каждого проверять принадлежность <tex> L_1 </tex>. Если хотя бы в одном разбиении все подслова будут принадлежать <tex> L_1 </tex>, то все слово принадлежит <tex> L_1^* </tex>, иначе {{---}} не принадлежит.

* Для языка <tex> L_1 L_2 : </tex>

<tex>p(x)</tex>
'''forall''' <tex>d_{1,2} :</tex> все возможные разбиения на две части
<tex>x_{d_1}x_{d_2} :</tex> текущее разбиение <tex>x</tex>
'''if''' <tex>(p_1(x_{d_1}) == 1 \land p_2(x_{d_2}) == 1)</tex>
'''return''' 1
'''return''' 0

Разрешитель будет перебирать все возможные разбиения на два слова и проверять принадлежность первого слова <tex> L_1 </tex> и второго слова <tex> L_2 </tex>. Если хотя бы для одного разбиения оба разрешителя вернут 1, то слово принадлежит <tex> L_1 L_2 </tex>, иначе {{---}} не принадлежит.
}}

{{Теорема
|statement=
Языки <tex> L_1, L_2 </tex> {{---}} перечислимы, тогда следующие языки перечислимы:

* Объединение <tex>L_1</tex> и <tex>L_2\ (L_1 \cup L_2)</tex>
* Пересечение <tex>L_1</tex> и <tex>L_2\ (L_1 \cap L_2)</tex>
* Декартово произведение <tex>L_1</tex> и <tex>L_2\ (L_1 \times L_2)</tex>
* Замыкание Клини <tex>L_1\ (L_1^*)</tex>
* Конкатенация <tex>L_1</tex> и <tex>L_2\ (L_1 L_2)</tex>

|proof=

Пусть <tex>p_1</tex> и <tex>p_2</tex> {{---}} полуразрешающие программы для языков <tex>L_1</tex> и <tex>L_2</tex> соответственно. Для доказательства достаточно написать полуразрешающую программу для каждого случая. Заметим, что <tex>p_1</tex> и <tex>p_2</tex> могут зависнуть при использовании в полуразрешающей программе для соответствующего языка, но это допустимо.

* Полуразрешающая программа для языка <tex> L_1 \cup L_2 :</tex>

<tex>p(x)</tex>
'''for''' <tex>k = 1 \ .. \ \infty</tex>
'''if''' <tex> (p_1(x)|_k == 1) \lor (p_2(x)|_k == 1) </tex>
'''return 1'''

* Для языка <tex> L_1 \cap L_2 :</tex>

<tex>p(x)</tex>
'''if''' <tex> (p_1(x) == 1) \land (p_2(x) == 1) </tex>
'''return 1'''

* Для языка <tex> L_1 \times L_2 :</tex>

<tex>p(\langle x, y \rangle)</tex>
'''if''' <tex> (p_1(x) == 1) \land (p_2(y) == 1) </tex>
'''return 1'''

* Для языка <tex> L_1^* :</tex>

<tex>p(x)</tex>
'''forall''' <tex>d_i :</tex> все возможные разбиения
<tex>x_{d_1}x_{d_2} \ .. \ x_{d_n} :</tex> текущее разбиение <tex>x</tex>
'''if''' <tex>(p_1(x_{d_1}) == 1) \land (p_1(x_{d_2}) == 1) \land \ ... \ \land (p_1(x_{d_n}) == 1)</tex>
'''return 1'''

* Для языка <tex> L_1 L_2 : </tex>

<tex>p(x)</tex>
'''forall''' <tex>d_{1,2} :</tex> все возможные разбиения на две части
<tex>x_{d_1}x_{d_2} :</tex> текущее разбиение <tex>x</tex>
'''if''' <tex>(p_1(x_{d_1}) == 1 \land p_2(x_{d_2}) == 1)</tex>
'''return 1'''
 
}}

{{Теорема
|statement=
Языки <tex> L_1, L_2 </tex> {{---}} перечислимы, тогда следующие языки могут быть не перечислимы:

* Дополнение <tex>L_1\ (\overline{L_1})</tex>
* Разность <tex>L_1</tex> и <tex>L_2\ (L_1 \backslash L_2)</tex>

|proof=

Рассмотрим язык <tex> \overline{L_1} </tex>. Предположим, что он перечислим. Тогда, имея какое-либо слово, мы можем одновременно запустить перечислители для <tex> L_1 </tex> и <tex> \overline{L_1} </tex>. В какой-то момент времени слово появится либо в выводе перечислителя для <tex> L_1 </tex>, либо в выводе перечислителя для <tex> \overline{L_1} </tex>. Тогда получится что <tex> L_1 </tex> разрешим, так как про любое слово мы можем узнать принадлежит оно <tex> L_1 </tex> или не принадлежит. Но мы знаем, что [[Разрешимые (рекурсивные) языки#Пример неразрешимого множества|существуют перечислимые, но не разрешимые языки]], следовательно, язык <tex> \overline{L_1} </tex> может быть не перечислим.

Теперь рассмотрим <tex> L_1 \backslash L_2 </tex>. В качестве <tex> L_1 </tex> возьмем язык, состоящий из всех слов. Тогда получится, что язык <tex> L_1 \backslash L_2 </tex> это <tex> \overline{L_2} </tex>. Про язык <tex> \overline{L_2} </tex> мы знаем, что он перечислим не всегда, следовательно и язык <tex> L_1 \backslash L_2 </tex> также не всегда перечислим.
}}

== Литература ==
* ''Верещагин Н. К., Шень А.'' '''Лекции по математической логике и теории алгоритов. Часть 3. Вычислимые функции''' {{---}} М.: МЦНМО, 1999

Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций

2011-12-20T06:52:57Z

Roman Livarsky:

{{Теорема
|statement=
Языки <tex> L_1, L_2 </tex> {{---}} разрешимы, тогда следующие языки разрешимы:

* Объединение <tex>L_1</tex> и <tex>L_2\ (L_1 \cup L_2)</tex>
* Пересечение <tex>L_1</tex> и <tex>L_2\ (L_1 \cap L_2)</tex>
* Дополнение <tex>L_1\ (\overline{L_1})</tex>
* Разность <tex>L_1</tex> и <tex>L_2\ (L_1 \backslash L_2)</tex>
* Декартово произведение <tex>L_1</tex> и <tex>L_2\ (L_1 \times L_2)</tex>
* Замыкание Клини <tex>L_1\ (L_1^*)</tex>
* Конкатенация <tex>L_1</tex> и <tex>L_2\ (L_1 L_2)</tex>

|proof=
Пусть <tex>p_1</tex> и <tex>p_2</tex> {{---}} разрешающие программы для языков
<tex>L_1</tex> и <tex>L_2</tex> соответственно. Для доказательства достаточно написать разрешающую программу (разрешитель) для каждого случая.

* Разрешающая программа для языка <tex> L_1 \cup L_2 :</tex>

<tex>p(x)</tex>
'''return''' <tex>(p_1(x) == 1) \lor (p_2(x) == 1)</tex>

* Для языка <tex> L_1 \cap L_2 :</tex>

<tex>p(x)</tex>
'''return''' <tex>(p_1(x) == 1) \land (p_2(x) == 1)</tex>

* Для языка <tex> \overline{L_1} :</tex>

<tex>p(x)</tex>
'''return''' <tex>(p_1(x) == 0)</tex>

* Для языка <tex> L_1 \backslash L_2 :</tex>

<tex>p(x)</tex>
'''return''' <tex>(p_1(x) == 1) \land (p_2(x) == 0)</tex>

* Для языка <tex> L_1 \times L_2 :</tex>

<tex>p(\langle x, y \rangle)</tex>
'''return''' <tex>(p_1(x) == 1) \land (p_2(y) == 1)</tex>

* Для языка <tex>L_1^* :</tex>

<tex>p(x)</tex>
'''forall''' <tex>d_i :</tex> все возможные разбиения
<tex>x_{d_1}x_{d_2} \ .. \ x_{d_n} :</tex> текущее разбиение <tex>x</tex>
'''if''' <tex>(p_1(x_{d_1}) == 1) \land (p_1(x_{d_2}) == 1) \land \ ... \ \land (p_1(x_{d_n}) == 1)</tex>
'''return''' 1
'''return''' 0

Разрешитель будет перебирать все возможные разбиения данного ему слова на подслова, и для каждого проверять принадлежность <tex> L_1 </tex>. Если хотя бы в одном разбиении все подслова будут принадлежать <tex> L_1 </tex>, то все слово принадлежит <tex> L_1^* </tex>, иначе {{---}} не принадлежит.

* Для языка <tex> L_1 L_2 : </tex>

<tex>p(x)</tex>
'''forall''' <tex>d_{1,2} :</tex> все возможные разбиения на две части
<tex>x_{d_1}x_{d_2} :</tex> текущее разбиение <tex>x</tex>
'''if''' <tex>(p_1(x_{d_1}) == 1 \land p_2(x_{d_2}) == 1)</tex>
'''return''' 1
'''return''' 0

Разрешитель будет перебирать все возможные разбиения на два слова и проверять принадлежность первого слова <tex> L_1 </tex> и второго слова <tex> L_2 </tex>. Если хотя бы для одного разбиения оба разрешителя вернут 1, то слово принадлежит <tex> L_1 L_2 </tex>, иначе {{---}} не принадлежит.
}}

{{Теорема
|statement=
Языки <tex> L_1, L_2 </tex> {{---}} перечислимы, тогда следующие языки перечислимы:

* Объединение <tex>L_1</tex> и <tex>L_2\ (L_1 \cup L_2)</tex>
* Пересечение <tex>L_1</tex> и <tex>L_2\ (L_1 \cap L_2)</tex>
* Декартово произведение <tex>L_1</tex> и <tex>L_2\ (L_1 \times L_2)</tex>
* Замыкание Клини <tex>L_1\ (L_1^*)</tex>
* Конкатенация <tex>L_1</tex> и <tex>L_2\ (L_1 L_2)</tex>

|proof=

Пусть <tex>p_1</tex> и <tex>p_2</tex> {{---}} полуразрешающие программы для языков <tex>L_1</tex> и <tex>L_2</tex> соответственно. Для доказательства достаточно написать полуразрешающую программу для каждого случая. Заметим, что <tex>p_1</tex> и <tex>p_2</tex> могут зависнуть при использовании в полуразрешающей программе для соответствующего языка, но это допустимо.

* Полуразрешающая программа для языка <tex> L_1 \cup L_2 :</tex>

<tex>p(x)</tex>
'''for''' <tex>k = 1 \ .. \ \infty</tex>
'''if''' <tex> (p_1(x)|_k == 1) \lor (p_2(x)|_k == 1) </tex>
'''return 1'''

* Для языка <tex> L_1 \cap L_2 :</tex>

<tex>p(x)</tex>
'''if''' <tex> (p_1(x) == 1) \land (p_2(x) == 1) </tex>
'''return 1'''

* Для языка <tex> L_1 \times L_2 :</tex>

<tex>p(\langle x, y \rangle)</tex>
'''if''' <tex> (p_1(x) == 1) \land (p_2(y) == 1) </tex>
'''return 1'''

* Для языка <tex> L_1^* :</tex>

<tex>p(x)</tex>
'''forall''' <tex>d_i :</tex> все возможные разбиения
<tex>x_{d_1}x_{d_2} \ .. \ x_{d_n} :</tex> текущее разбиение <tex>x</tex>
'''if''' <tex>(p_1(x_{d_1}) == 1) \land (p_1(x_{d_2}) == 1) \land \ ... \ \land (p_1(x_{d_n}) == 1)</tex>
'''return 1'''

* Для языка <tex> L_1 L_2 : </tex>

<tex>p(x)</tex>
'''forall''' <tex>d_{1,2} :</tex> все возможные разбиения на две части
<tex>x_{d_1}x_{d_2} :</tex> текущее разбиение <tex>x</tex>
'''if''' <tex>(p_1(x_{d_1}) == 1 \land p_2(x_{d_2}) == 1)</tex>
'''return 1'''
 
}}

{{Теорема
|statement=
Языки <tex> L_1, L_2 </tex> {{---}} перечислимы, тогда следующие языки могут быть не перечислимы:

* Дополнение <tex>L_1\ (\overline{L_1})</tex>
* Разность <tex>L_1</tex> и <tex>L_2\ (L_1 \backslash L_2)</tex>

|proof=

Рассмотрим язык <tex> \overline{L_1} </tex>. Предположим, что он перечислим. Тогда, имея какое-либо слово, мы можем одновременно запустить перечислители для <tex> L_1 </tex> и <tex> \overline{L_1} </tex>. В какой-то момент времени слово появится либо в выводе перечислителя для <tex> L_1 </tex>, либо в выводе перечислителя для <tex> \overline{L_1} </tex>. Тогда получится что <tex> L_1 </tex> разрешим, так как про любое слово мы можем узнать принадлежит оно <tex> L_1 </tex> или не принадлежит. Но мы знаем, что [[Разрешимые (рекурсивные) языки#Пример неразрешимого множества|существуют перечислимые, но не разрешимые языки]], следовательно, язык <tex> \overline{L_1} </tex> может быть не перечислим.

Теперь рассмотрим <tex> L_1 \backslash L_2 </tex>. В качестве <tex> L_1 </tex> возьмем язык, состоящий из всех слов. Тогда получится, что язык <tex> L_1 \backslash L_2 </tex> это <tex> \overline{L_2} </tex>. Про язык <tex> \overline{L_2} </tex> мы знаем, что он перечислим не всегда, следовательно и язык <tex> L_1 \backslash L_2 </tex> также не всегда перечислим.
}}

== Литература ==
* ''Верещагин Н. К., Шень А.'' '''Лекции по математической логике и теории алгоритов. Часть 3. Вычислимые функции''' {{---}} М.: МЦНМО, 1999

Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций

2011-12-20T06:50:13Z

Roman Livarsky:

{{Теорема
|statement=
Языки <tex> L_1, L_2 </tex> {{---}} разрешимы, тогда следующие языки разрешимы:

* Объединение <tex>L_1</tex> и <tex>L_2\ (L_1 \cup L_2)</tex>
* Пересечение <tex>L_1</tex> и <tex>L_2\ (L_1 \cap L_2)</tex>
* Дополнение <tex>L_1\ (\overline{L_1})</tex>
* Разность <tex>L_1</tex> и <tex>L_2\ (L_1 \backslash L_2)</tex>
* Декартово произведение <tex>L_1</tex> и <tex>L_2\ (L_1 \times L_2)</tex>
* Замыкание Клини <tex>L_1\ (L_1^*)</tex>
* Конкатенация <tex>L_1</tex> и <tex>L_2\ (L_1 L_2)</tex>

|proof=
Пусть <tex>p_1</tex> и <tex>p_2</tex> {{---}} разрешающие программы для языков
<tex>L_1</tex> и <tex>L_2</tex> соответственно. Для доказательства достаточно написать разрешающую программу (разрешитель) для каждого случая.

* Разрешающая программа для языка <tex> L_1 \cup L_2 :</tex>

<tex>p(x)</tex>
'''return''' <tex>(p_1(x) == 1) \lor (p_2(x) == 1)</tex>

* Для языка <tex> L_1 \cap L_2 :</tex>

<tex>p(x)</tex>
'''return''' <tex>(p_1(x) == 1) \land (p_2(x) == 1)</tex>

* Для языка <tex> \overline{L_1} :</tex>

<tex>p(x)</tex>
'''return''' <tex>(p_1(x) == 0)</tex>

* Для языка <tex> L_1 \backslash L_2 :</tex>

<tex>p(x)</tex>
'''return''' <tex>(p_1(x) == 1) \land (p_2(x) == 0)</tex>

* Для языка <tex> L_1 \times L_2 :</tex>

<tex>p(\langle x, y \rangle)</tex>
'''return''' <tex>(p_1(x) == 1) \land (p_2(y) == 1)</tex>

* Для языка <tex>L_1^* :</tex>

<tex>p(x)</tex>
'''forall''' <tex>d_i :</tex> все возможные разбиения
<tex>x_{d_1}x_{d_2} \ .. \ x_{d_n} :</tex> текущее разбиение <tex>x</tex>
'''if''' <tex>(p_1(x_{d_1}) == 1) \land (p_1(x_{d_2}) == 1) \land \ ... \ \land (p_1(x_{d_n}) == 1)</tex>
'''return''' 1
'''return''' 0

Разрешитель будет перебирать все возможные разбиения данного ему слова на подслова, и для каждого проверять принадлежность <tex> L_1 </tex>. Если хотя бы в одном разбиении все подслова будут принадлежать <tex> L_1 </tex>, то все слово принадлежит <tex> L_1^* </tex>, иначе {{---}} не принадлежит.

* Для языка <tex> L_1 L_2 : </tex>

<tex>p(x)</tex>
'''forall''' <tex>d_{1,2} :</tex> все возможные разбиения на две части
<tex>x_{d_1}x_{d_2} :</tex> текущее разбиение <tex>x</tex>
'''if''' <tex>(p_1(x_{d_1}) == 1 \land p_2(x_{d_2}) == 1)</tex>
'''return''' 1
'''return''' 0

Разрешитель будет перебирать все возможные разбиения на два слова и проверять принадлежность первого слова <tex> L_1 </tex> и второго слова <tex> L_2 </tex>. Если хотя бы для одного разбиения оба разрешителя вернут 1, то слово принадлежит <tex> L_1 L_2 </tex>, иначе {{---}} не принадлежит.
}}

{{Теорема
|statement=
Языки <tex> L_1, L_2 </tex> {{---}} перечислимы, тогда следующие языки перечислимы:

* Объединение <tex>L_1</tex> и <tex>L_2\ (L_1 \cup L_2)</tex>
* Пересечение <tex>L_1</tex> и <tex>L_2\ (L_1 \cap L_2)</tex>
* Декартово произведение <tex>L_1</tex> и <tex>L_2\ (L_1 \times L_2)</tex>
* Замыкание Клини <tex>L_1\ (L_1^*)</tex>
* Конкатенация <tex>L_1</tex> и <tex>L_2\ (L_1 L_2)</tex>

|proof=

Пусть <tex>p_1</tex> и <tex>p_2</tex> {{---}} полуразрешающие программы для языков <tex>L_1</tex> и <tex>L_2</tex> соответственно. Для доказательства достаточно написать полуразрешающую программу для каждого случая. Заметим, что <tex>p_1</tex> и <tex>p_2</tex> могут зависнуть при использовании в полуразрешающей программе для соответствующего языка, но это допустимо.

* Для языка <tex> L_1 \cup L_2 :</tex>

<tex>p(x)</tex>
'''for''' <tex>k = 1 \ .. \ \infty</tex>
'''if''' <tex> (p_1(x)|_k == 1) \lor (p_2(x)|_k == 1) </tex>
'''return 1'''

* Для языка <tex> L_1 \cap L_2 :</tex>

<tex>p(x)</tex>
'''if''' <tex> (p_1(x) == 1) \land (p_2(x) == 1) </tex>
'''return 1'''

* Для языка <tex> L_1 \times L_2 :</tex>

<tex>p(\langle x, y \rangle)</tex>
'''if''' <tex> (p_1(x) == 1) \land (p_2(y) == 1) </tex>
'''return 1'''

* Для языка <tex> L_1^* :</tex>

<tex>p(x)</tex>
'''forall''' <tex>d_i :</tex> все возможные разбиения
<tex>x_{d_1}x_{d_2} \ .. \ x_{d_n} :</tex> текущее разбиение <tex>x</tex>
'''if''' <tex>(p_1(x_{d_1}) == 1) \land (p_1(x_{d_2}) == 1) \land \ ... \ \land (p_1(x_{d_n}) == 1)</tex>
'''return 1'''

* Для языка <tex> L_1 L_2 : </tex>

<tex>p(x)</tex>
'''forall''' <tex>d_{1,2} :</tex> все возможные разбиения на две части
<tex>x_{d_1}x_{d_2} :</tex> текущее разбиение <tex>x</tex>
'''if''' <tex>(p_1(x_{d_1}) == 1 \land p_2(x_{d_2}) == 1)</tex>
'''return 1'''
 
}}

{{Теорема
|statement=
Языки <tex> L_1, L_2 </tex> {{---}} перечислимы, тогда следующие языки могут быть не перечислимы:

* Дополнение <tex>L_1\ (\overline{L_1})</tex>
* Разность <tex>L_1</tex> и <tex>L_2\ (L_1 \backslash L_2)</tex>

|proof=

Рассмотрим язык <tex> \overline{L_1} </tex>. Предположим, что он перечислим. Тогда, имея какое-либо слово, мы можем одновременно запустить перечислители для <tex> L_1 </tex> и <tex> \overline{L_1} </tex>. В какой-то момент времени слово появится либо в выводе перечислителя для <tex> L_1 </tex>, либо в выводе перечислителя для <tex> \overline{L_1} </tex>. Тогда получится что <tex> L_1 </tex> разрешим, так как про любое слово мы можем узнать принадлежит оно <tex> L_1 </tex> или не принадлежит. Но мы знаем, что [[Разрешимые (рекурсивные) языки#Пример неразрешимого множества|существуют перечислимые, но не разрешимые языки]], следовательно, язык <tex> \overline{L_1} </tex> может быть не перечислим.

Теперь рассмотрим <tex> L_1 \backslash L_2 </tex>. В качестве <tex> L_1 </tex> возьмем язык, состоящий из всех слов. Тогда получится, что язык <tex> L_1 \backslash L_2 </tex> это <tex> \overline{L_2} </tex>. Про язык <tex> \overline{L_2} </tex> мы знаем, что он перечислим не всегда, следовательно и язык <tex> L_1 \backslash L_2 </tex> также не всегда перечислим.
}}

== Литература ==
* ''Верещагин Н. К., Шень А.'' '''Лекции по математической логике и теории алгоритов. Часть 3. Вычислимые функции''' {{–--}} М.: МЦНМО, 1999

Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций

2011-12-20T06:37:11Z

Roman Livarsky:

{{Теорема
|statement=
Языки <tex> L_1, L_2 </tex> –- разрешимы, тогда следующие языки разрешимы:

* Объединение <tex>L_1</tex> и <tex>L_2\ (L_1 \cup L_2)</tex>
* Пересечение <tex>L_1</tex> и <tex>L_2\ (L_1 \cap L_2)</tex>
* Дополнение <tex>L_1\ (\overline{L_1})</tex>
* Разность <tex>L_1</tex> и <tex>L_2\ (L_1 \backslash L_2)</tex>
* Декартово произведение <tex>L_1</tex> и <tex>L_2\ (L_1 \times L_2)</tex>
* Замыкание Клини <tex>L_1\ (L_1^*)</tex>
* Конкатенация <tex>L_1</tex> и <tex>L_2\ (L_1 L_2)</tex>

|proof=
Пусть <tex>p_1</tex> и <tex>p_2</tex> — разрешающие программы для языков
<tex>L_1</tex> и <tex>L_2</tex> соответственно. Для доказательства достаточно написать разрешающую программу (разрешитель) для каждого случая.

* Разрешающая программа для языка <tex> L_1 \cup L_2 :</tex>

<tex>p(x)</tex>
'''return''' <tex>(p_1(x) == 1) \lor (p_2(x) == 1)</tex>

* Для языка <tex> L_1 \cap L_2 :</tex>

<tex>p(x)</tex>
'''return''' <tex>(p_1(x) == 1) \land (p_2(x) == 1)</tex>

* Для языка <tex> \overline{L_1} :</tex>

<tex>p(x)</tex>
'''return''' <tex>(p_1(x) == 0)</tex>

* Для языка <tex> L_1 \backslash L_2 :</tex>

<tex>p(x)</tex>
'''return''' <tex>(p_1(x) == 1) \land (p_2(x) == 0)</tex>

* Для языка <tex> L_1 \times L_2 :</tex>

<tex>p(\langle x, y \rangle)</tex>
'''return''' <tex>(p_1(x) == 1) \land (p_2(y) == 1)</tex>

* Для языка <tex>L_1^* :</tex>

<tex>p(x)</tex>
'''forall''' <tex>d_i :</tex> все возможные разбиения
<tex>x_{d_1}x_{d_2} \ .. \ x_{d_n} :</tex> текущее разбиение <tex>x</tex>
'''if''' <tex>(p_1(x_{d_1}) == 1) \land (p_1(x_{d_2}) == 1) \land \ ... \ \land (p_1(x_{d_n}) == 1)</tex>
'''return''' 1
'''return''' 0

Разрешитель будет перебирать все возможные разбиения данного ему слова на подслова, и для каждого проверять принадлежность <tex> L_1 </tex>. Если хотя бы в одном разбиении все подслова будут принадлежать <tex> L_1 </tex>, то все слово принадлежит <tex> L_1^* </tex>, иначе — не принадлежит.

* Для языка <tex> L_1 L_2 : </tex>

<tex>p(x)</tex>
'''forall''' <tex>d_{1,2} :</tex> все возможные разбиения на две части
<tex>x_{d_1}x_{d_2} :</tex> текущее разбиение <tex>x</tex>
'''if''' <tex>(p_1(x_{d_1}) == 1 \land p_2(x_{d_2}) == 1)</tex>
'''return''' 1
'''return''' 0

Разрешитель будет перебирать все возможные разбиения на два слова и проверять принадлежность первого слова <tex> L_1 </tex> и второго слова <tex> L_2 </tex>. Если хотя бы для одного разбиения оба разрешителя вернут 1, то слово принадлежит <tex> L_1 L_2 </tex>, иначе — не принадлежит.
}}

{{Теорема
|statement=
Языки <tex> L_1, L_2 </tex> –- перечислимы, тогда следующие языки перечислимы:

* Объединение <tex>L_1</tex> и <tex>L_2\ (L_1 \cup L_2)</tex>
* Пересечение <tex>L_1</tex> и <tex>L_2\ (L_1 \cap L_2)</tex>
* Декартово произведение <tex>L_1</tex> и <tex>L_2\ (L_1 \times L_2)</tex>
* Замыкание Клини <tex>L_1\ (L_1^*)</tex>
* Конкатенация <tex>L_1</tex> и <tex>L_2\ (L_1 L_2)</tex>

|proof=

Пусть <tex>p_1</tex> и <tex>p_2</tex> — полуразрешающие программы для языков <tex>L_1</tex> и <tex>L_2</tex> соответственно. Для доказательства достаточно написать полуразрешающую программу для каждого случая. Заметим, что <tex>p_1</tex> и <tex>p_2</tex> могут зависнуть при использовании в полуразрешающей программе для соответствующего языка, но это допустимо.

* Для языка <tex> L_1 \cup L_2 :</tex>

<tex>p(x)</tex>
'''for''' <tex>k = 1 \ .. \ \infty</tex>
'''if''' <tex> (p_1(x)|_k == 1) \lor (p_2(x)|_k == 1) </tex>
'''return 1'''

* Для языка <tex> L_1 \cap L_2 :</tex>

<tex>p(x)</tex>
'''if''' <tex> (p_1(x) == 1) \land (p_2(x) == 1) </tex>
'''return 1'''

* Для языка <tex> L_1 \times L_2 :</tex>

<tex>p(\langle x, y \rangle)</tex>
'''if''' <tex> (p_1(x) == 1) \land (p_2(y) == 1) </tex>
'''return 1'''

* Для языка <tex> L_1^* :</tex>

<tex>p(x)</tex>
'''forall''' <tex>d_i :</tex> все возможные разбиения
<tex>x_{d_1}x_{d_2} \ .. \ x_{d_n} :</tex> текущее разбиение <tex>x</tex>
'''if''' <tex>(p_1(x_{d_1}) == 1) \land (p_1(x_{d_2}) == 1) \land \ ... \ \land (p_1(x_{d_n}) == 1)</tex>
'''return 1'''

* Для языка <tex> L_1 L_2 : </tex>

<tex>p(x)</tex>
'''forall''' <tex>d_{1,2} :</tex> все возможные разбиения на две части
<tex>x_{d_1}x_{d_2} :</tex> текущее разбиение <tex>x</tex>
'''if''' <tex>(p_1(x_{d_1}) == 1 \land p_2(x_{d_2}) == 1)</tex>
'''return 1'''
 
}}

{{Теорема
|statement=
Языки <tex> L_1, L_2 </tex> –- перечислимы, тогда следующие языки могут быть не перечислимы:

* Дополнение <tex>L_1\ (\overline{L_1})</tex>
* Разность <tex>L_1</tex> и <tex>L_2\ (L_1 \backslash L_2)</tex>

|proof=

Рассмотрим язык <tex> \overline{L_1} </tex>. Предположим, что он перечислим. Тогда, имея какое-либо слово, мы можем одновременно запустить перечислители для <tex> L_1 </tex> и <tex> \overline{L_1} </tex>. В какой-то момент времени слово появится либо в выводе перечислителя для <tex> L_1 </tex>, либо в выводе перечислителя для <tex> \overline{L_1} </tex>. Тогда получится что <tex> L_1 </tex> разрешим, так как про любое слово мы можем узнать принадлежит оно <tex> L_1 </tex> или не принадлежит. Но мы знаем, что [[Разрешимые (рекурсивные) языки#Пример неразрешимого множества|существуют перечислимые, но не разрешимые языки]], следовательно, язык <tex> \overline{L_1} </tex> может быть не перечислим.

Теперь рассмотрим <tex> L_1 \backslash L_2 </tex>. В качестве <tex> L_1 </tex> возьмем язык, состоящий из всех слов. Тогда получится, что язык <tex> L_1 \backslash L_2 </tex> это <tex> \overline{L_2} </tex>. Про язык <tex> \overline{L_2} </tex> мы знаем, что он перечислим не всегда, следовательно и язык <tex> L_1 \backslash L_2 </tex> также не всегда перечислим.
}}

== Литература ==
* ''Верещагин Н. К., Шень А.'' '''Лекции по математической логике и теории алгоритов. Часть 3. Вычислимые функции''' — М.: МЦНМО, 1999

Обсуждение:Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций

2011-12-19T21:46:49Z

Roman Livarsky:

Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций

2011-12-19T21:44:11Z

Roman Livarsky:

{{Теорема
|statement=
Языки <tex> L_1, L_2 </tex> –- разрешимы, тогда следующие языки разрешимы:

* Объединение <tex>L_1</tex> и <tex>L_2\ (L_1 \cup L_2)</tex>
* Пересечение <tex>L_1</tex> и <tex>L_2\ (L_1 \cap L_2)</tex>
* Дополнение <tex>L_1\ (\overline{L_1})</tex>
* Разность <tex>L_1</tex> и <tex>L_2\ (L_1 \backslash L_2)</tex>
* Декартово произведение <tex>L_1</tex> и <tex>L_2\ (L_1 \times L_2)</tex>
* Замыкание Клини <tex>L_1\ (L_1^*)</tex>
* Конкатенация <tex>L_1</tex> и <tex>L_2\ (L_1 L_2)</tex>

|proof=
Пусть <tex>p_1</tex> и <tex>p_2</tex> — разрешающие программы для языков
<tex>L_1</tex> и <tex>L_2</tex> соответственно. Для доказательства достаточно написать разрешающую программу (разрешитель) для каждого случая.

* Разрешающая программа для языка <tex> L_1 \cup L_2 :</tex>

<tex>p(x)</tex>
'''return''' <tex>(p_1(x) == 1) \lor (p_2(x) == 1)</tex>

* Для языка <tex> L_1 \cap L_2 :</tex>

<tex>p(x)</tex>
'''return''' <tex>(p_1(x) == 1) \land (p_2(x) == 1)</tex>

* Для языка <tex> \overline{L_1} :</tex>

<tex>p(x)</tex>
'''return''' <tex>(p_1(x) == 0)</tex>

* Для языка <tex> L_1 \backslash L_2 :</tex>

<tex>p(x)</tex>
'''return''' <tex>(p_1(x) == 1) \land (p_2(x) == 0)</tex>

* Для языка <tex> L_1 \times L_2 :</tex>

<tex>p(\langle x, y \rangle)</tex>
'''return''' <tex>(p_1(x) == 1) \land (p_2(y) == 1)</tex>

* Для языка <tex>L_1^* :</tex>

<tex>p(x)</tex>
'''forall''' <tex>x_i :</tex> разбиение <tex>x</tex>
'''if''' <tex>(p_1(x_1) == 1) \land (p_1(x_2) == 1) \land \ ... \ \land (p_1(x_n) == 1)</tex>
'''return''' 1
'''return''' 0

Разрешитель будет перебирать все возможные разбиения данного ему слова на подслова, и для каждого проверять принадлежность <tex> L_1 </tex>. Если хотя бы в одном разбиении все подслова будут принадлежать <tex> L_1 </tex>, то все слово принадлежит <tex> L_1^* </tex>, иначе — не принадлежит.

* Для языка <tex> L_1 L_2 : </tex>

<tex>p(x)</tex>
'''forall''' <tex>x_1, x_2 :</tex> разбиение <tex>x</tex>
'''if''' <tex>(p_1(x_1) == 1 \land p_2(x_2) == 1)</tex>
'''return''' 1
'''return''' 0

Разрешитель будет перебирать все возможные разбиения на два слова и проверять принадлежность первого слова <tex> L_1 </tex> и второго слова <tex> L_2 </tex>. Если хотя бы для одного разбиения оба разрешителя вернут 1, то слово принадлежит <tex> L_1 L_2 </tex>, иначе — не принадлежит.
}}

{{Теорема
|statement=
Языки <tex> L_1, L_2 </tex> –- перечислимы, тогда следующие языки перечислимы:

* Объединение <tex>L_1</tex> и <tex>L_2\ (L_1 \cup L_2)</tex>
* Пересечение <tex>L_1</tex> и <tex>L_2\ (L_1 \cap L_2)</tex>
* Декартово произведение <tex>L_1</tex> и <tex>L_2\ (L_1 \times L_2)</tex>
* Замыкание Клини <tex>L_1\ (L_1^*)</tex>
* Конкатенация <tex>L_1</tex> и <tex>L_2\ (L_1 L_2)</tex>

|proof=

Пусть <tex>p_1</tex> и <tex>p_2</tex> — полуразрешающие программы для языков <tex>L_1</tex> и <tex>L_2</tex> соответственно. Для доказательства достаточно написать полуразрешающую или перечисляющую программу для каждого случая. Для некоторых языков предоставим оба варианта. Заметим, что <tex>p_1</tex> и <tex>p_2</tex> могут зависнуть при использовании в полуразрешающей программе для соответствующего языка, но это допустимо.

* Для языка <tex> L_1 \cup L_2 :</tex>

полуразрешающая программа:

<tex>p(x)</tex>
'''if''' <tex> (p_1(x) == 1) \lor (p_2(x) == 1) </tex>
'''return 1'''

Перечислитель же для этого языка будет по очереди на один шаг запускать перечислители для <tex>L_1</tex> и <tex>L_2</tex> и выдавать по очереди слова из <tex>L_1</tex> и <tex>L_2</tex> соответственно.

* Для языка <tex> L_1 \cap L_2 :</tex>

полуразрешающая программа:

<tex>p(x)</tex>
'''if''' <tex> (p_1(x) == 1) \land (p_2(x) == 1) </tex>
'''return 1'''

* Для языка <tex> L_1 \times L_2 :</tex>

полуразрешающая программа:

<tex>p(\langle x, y \rangle)</tex>
'''if''' <tex> (p_1(x) == 1) \land (p_2(y) == 1) </tex>
'''return 1'''

* Для языка <tex> L_1^* :</tex>

полуразрешающая программа (по аналогии с <tex>L_1^*</tex> для разрешимого <tex>L_1</tex>):

<tex>p(x)</tex>
'''forall''' <tex>x_i :</tex> разбиение <tex>x</tex>
'''if''' <tex>(p_1(x_1) == 1) \land (p_1(x_2) == 1) \land \ ... \ \land (p_1(x_n) == 1)</tex>
'''return''' 1

Перечислитель же строится следующим образом: запускаем перечислитель для <tex> L_1 </tex> в цикле по тайм-лимиту и запоминаем выданные им слова. При выдаче каждого нового слова перебираем все возможные перестановки уже выданных слов и выдаем их.

* Для языка <tex> L_1 L_2 : </tex>

полуразрешающая программа:

<tex>p(x)</tex>
'''forall''' <tex>x_1, x_2 :</tex> разбиение <tex>x</tex>
'''if''' <tex>(p_1(x_1) == 1 \land p_2(x_2) == 1)</tex>
'''return''' 1

Перечислитель же для <tex> L_1 L_2 </tex> строим следующим образом: запускаем одновременно перечислители для <tex> L_1 </tex> и <tex> L_2 </tex>, запоминая все выданные слова. При выдаче новых слов перебираем все возможные пары из запомненных слов и выдаем их конкатенацию.
}}

{{Теорема
|statement=
Языки <tex> L_1, L_2 </tex> –- перечислимы, тогда следующие языки могут быть не перечислимы:

* Дополнение <tex>L_1\ (\overline{L_1})</tex>
* Разность <tex>L_1</tex> и <tex>L_2\ (L_1 \backslash L_2)</tex>

|proof=

Рассмотрим язык <tex> \overline{L_1} </tex>. Предположим, что он перечислим. Тогда имея какое-либо слово, мы можем одновременно запустить перечислители для <tex> L_1 </tex> и <tex> \overline{L_1} </tex>. В какой-то момент времени слово появится либо в выводе перечислителя для <tex> L_1 </tex>, либо в выводе перечислителя для <tex> \overline{L_1} </tex>. Тогда получится что <tex> L_1 </tex> разрешим, так как про любое слово мы можем узнать принадлежит оно <tex> L_1 </tex> или не принадлежит. Но мы знаем, что существуют перечислимые, но не разрешимые языки, следовательно, язык <tex> \overline{L_1} </tex> может быть не перечислим.

Теперь рассмотрим <tex> L_1 \backslash L_2 </tex>. В качестве <tex> L_1 </tex> возьмем язык, состоящий из всех слов. Тогда получится, что язык <tex> L_1 \backslash L_2 </tex> это <tex> \overline{L_2} </tex>. Про язык <tex> \overline{L_2} </tex> мы знаем, что он перечислим не всегда, следовательно и язык <tex> L_1 \backslash L_2 </tex> также не всегда перечислим.
}}

== Литература ==
* ''Верещагин Н. К., Шень А.'' '''Лекции по математической логике и теории алгоритов. Часть 3. Вычислимые функции''' — М.: МЦНМО, 1999

Обсуждение:Характеристика перечислимых множеств через вычислимые функции

2011-12-19T21:40:50Z

Roman Livarsky:

Претензия по сути: отсутствует доказательство 3 <tex>\Rightarrow</tex> 2.

По оформлению претензий много.
В определениях: во-первых, после двоеточия пишется строчная буква, даже на следующей строке. Во-вторых, перед причастным оборотом ставится запятая (первое определение). В-третьих, слова «вычислимая функция» лучше сделать ссылкой на соответствующую статью.

В доказательстве теоремы: во-первых, в псевдокоде не стоит после if писать then, тем более на следующей строке.
Во-вторых, в пункте «2 <tex>\Rightarrow</tex> 1» есть второе предложение, нуждающееся в переформулировке. <tex>p(x)|_{TL}</tex> — это не «запустить», это некоторый объект, как видно из следующего предложения. Короче, с этим надо что-то делать. И да, зачем вокруг тире по 3 пробела?

И список литературы выглядит криво — почему вместо тире два дефиса? [[Участник:Berezhkovskaya|Алёна]]

Пожалуйста, если что-то исправляешь — отмечай здесь.
Знаешь, стало не сильно лучше. Да, после двоеточия идет строчная буква, но вот после точки — прописная. Так что определение №4 верни как было.
Теперь комментарии к <tex>p(x)|_{TL}</tex> вообще исчезли. Верни обратно пояснение, просто напиши его понятным языком.
По прежнему нет доказательства 3 <tex>\Rightarrow</tex> 2. [[Участник:Berezhkovskaya|Алёна]]

Доказательство 3 <tex>\Rightarrow</tex> 2 : 3 <tex>\Rightarrow</tex> 1 <tex>\Rightarrow</tex> 4 <tex>\Rightarrow</tex> 2. Разве нет? Остальное исправил.
[[Участник:Roman Livarsky|Рома]]

Изменил определение для <tex>p(x)|_{TL}</tex>.
[[Участник:Roman Livarsky|Рома]]

Характеристика перечислимых множеств через вычислимые функции

2011-12-19T21:37:37Z

Roman Livarsky:

{{Определение
|definition=Множество <tex>X</tex> называется перечислимым, если выполняется хотя бы одно условие из приведенных ниже:
# существует программа, перечисляющая все элементы <tex>X</tex> в произвольном порядке.
# <tex>X</tex> является областью определения [[Вычислимые функции|вычиcлимой функции]] <tex>f</tex>.
# <tex>X</tex> является областью значений [[Вычислимые функции|вычиcлимой функции]] <tex>f</tex>.
# Функция <tex>f_X(x) = \begin{cases}
1, & x \in X \\
\bot, & x \notin X
\end{cases}</tex> — вычислима.
}}

{{Теорема
|statement=
Определения ''1'', ''2'', ''3'', ''4'' эквивалентны.
|proof=
*1 <tex>\Rightarrow</tex> 4

Пусть <tex>p</tex> — программа, перечисляющая <tex>X</tex>.

Приведем программу <tex>q</tex>, вычисляющую функцию <tex>f_X(x):</tex>

<tex>q(x)</tex>
'''for''' <tex>k = 1 \ .. \ \infty</tex>
'''if''' <tex> p(k) == x </tex>
'''return''' 1

*2 <tex>\Rightarrow</tex> 1, 3 <tex>\Rightarrow</tex> 1

Пусть <tex>X</tex> — область определения [[Вычислимые функции|вычислимой функции]] <tex>f</tex>, вычисляемой программой <tex>p</tex>.

Введем обозначение: <tex>p(x)|_{TL}</tex> — программа <tex>p(x)</tex>, запускаемая на <tex>TL</tex> секунд. Если <tex>p(x)|_{TL}</tex> за <tex>TL</tex> секунд так и не вернула значение, то считаем, что это значение равно <tex>\bot</tex>.

Тогда <tex>X</tex> перечисляется такой программой:

<tex>q()</tex>
'''for''' <tex> TL = 1 \ .. \ \infty </tex>
'''for''' <tex> k = 1 \ ..\ TL</tex>
'''if''' <tex>p(k)|_{TL} \neq \bot </tex>
'''print'''<tex>(k)</tex>

Если print<tex>(k)</tex> заменить на print(<tex>p(k)|_{TL}</tex>), то <tex>q</tex> станет перечислять область значений <tex>f(x)</tex>.

*4 <tex>\Rightarrow</tex> 2, 4 <tex>\Rightarrow</tex> 3

Пусть дана <tex>f_X(x)</tex>.

Введем новую функцию <tex>g(x) = x</tex>, если <tex>f_X(x) \neq \bot</tex>.

Очевидно, она вычислима, и ее область определения и область значений совпадают с <tex>X</tex>.

}}

== Литература ==
* ''Верещагин Н. К., Шень А.'' '''Лекции по математической логике и теории алгоритов. Часть 3. Вычислимые функции''' — М.: МЦНМО, 1999

Обсуждение:Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций

2011-12-19T03:32:32Z

Roman Livarsky:

Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций

2011-12-19T03:28:51Z

Roman Livarsky:

{{Теорема
|statement=
Языки <tex> L_1, L_2 </tex> –- разрешимы, тогда следующие языки разрешимы:

* Объединение <tex>L_1</tex> и <tex>L_2\ (L_1 \cup L_2)</tex>
* Пересечение <tex>L_1</tex> и <tex>L_2\ (L_1 \cap L_2)</tex>
* Дополнение <tex>L_1\ (\overline{L_1})</tex>
* Разность <tex>L_1</tex> и <tex>L_2\ (L_1 \backslash L_2)</tex>
* Декартово произведение <tex>L_1</tex> и <tex>L_2\ (L_1 \times L_2)</tex>
* Замыкание Клини <tex>L_1\ (L_1^*)</tex>
* Конкатенация <tex>L_1</tex> и <tex>L_2\ (L_1 L_2)</tex>

|proof=
Пусть <tex>p_1</tex> и <tex>p_2</tex> — разрешающие программы для языков
<tex>L_1</tex> и <tex>L_2</tex> соответственно. Для доказательства достаточно написать разрешающую программу (разрешитель) для каждого случая.

* Разрешающая программа для языка <tex> L_1 \cup L_2 :</tex>

<tex>p(x)</tex>
'''return''' <tex>(p_1(x) == 1) \lor (p_2(x) == 1)</tex>

* Для языка <tex> L_1 \cap L_2 :</tex>

<tex>p(x)</tex>
'''return''' <tex>(p_1(x) == 1) \land (p_2(x) == 1)</tex>

* Для языка <tex> \overline{L_1} :</tex>

<tex>p(x)</tex>
'''return''' <tex>(p_1(x) == 0)</tex>

* Для языка <tex> L_1 \backslash L_2 :</tex>

<tex>p(x)</tex>
'''return''' <tex>(p_1(x) == 1) \land (p_2(x) == 0)</tex>

* Для языка <tex> L_1 \times L_2 :</tex>

<tex>p(\langle x, y \rangle)</tex>
'''return''' <tex>(p_1(x) == 1) \land (p_2(y) == 1)</tex>

* Для языка <tex>L_1^* :</tex>

<tex>p(x)</tex>
'''forall''' <tex>x_i :</tex> разбиение <tex>x</tex>
'''if''' <tex>(p_1(x_1) == 1) \land (p_1(x_2) == 1) \land \ ... \ \land (p_1(x_n) == 1)</tex>
'''return''' 1
'''return''' 0

Разрешитель будет перебирать все возможные разбиения данного ему слова на подслова, и для каждого проверять принадлежность <tex> L_1 </tex>. Если хотя бы в одном разбиении все подслова будут принадлежать <tex> L_1 </tex>, то все слово принадлежит <tex> L_1^* </tex>, иначе — не принадлежит.

* Для языка <tex> L_1 L_2 : </tex>

<tex>p(x)</tex>
'''forall''' <tex>x_1, x_2 :</tex> разбиение <tex>x</tex>
'''if''' <tex>(p_1(x_1) == 1 \land p_2(x_2) == 1)</tex>
'''return''' 1
'''return''' 0

Разрешитель будет перебирать все возможные разбиения на два слова и проверять принадлежность первого слова <tex> L_1 </tex> и второго слова <tex> L_2 </tex>. Если хотя бы для одного разбиения оба разрешателя вернут 1, то слово принадлежит <tex> L_1 L_2 </tex>, иначе — не принадлежит.
}}

{{Теорема
|statement=
Языки <tex> L_1, L_2 </tex> –- перечислимы, тогда следующие языки перечислимы:

* Объединение <tex>L_1</tex> и <tex>L_2\ (L_1 \cup L_2)</tex>
* Пересечение <tex>L_1</tex> и <tex>L_2\ (L_1 \cap L_2)</tex>
* Декартово произведение <tex>L_1</tex> и <tex>L_2\ (L_1 \times L_2)</tex>
* Замыкание Клини <tex>L_1\ (L_1^*)</tex>
* Конкатенация <tex>L_1</tex> и <tex>L_2\ (L_1 L_2)</tex>

|proof=

Пусть <tex>p_1</tex> и <tex>p_2</tex> — полуразрешающие программы для языков <tex>L_1</tex> и <tex>L_2</tex> соответственно. Для доказательства достаточно написать полуразрешающую или перечисляющую программу для каждого случая. Для некоторых языков предоставим оба варианта. Заметим, что <tex>p_1</tex> и <tex>p_2</tex> могут зависнуть при использовании в полуразрешающей программе для соответствующего языка, но это допустимо.

* Для языка <tex> L_1 \cup L_2 :</tex>

полуразрешающая программа:

<tex>p(x)</tex>
'''if''' <tex> (p_1(x) == 1) \lor (p_2(x) == 1) </tex>
'''return 1'''

Перечислитель же для этого языка будет по очереди на один шаг запускать перечислители для <tex>L_1</tex> и <tex>L_2</tex> и выдавать по очереди слова из <tex>L_1</tex> и <tex>L_2</tex> соответственно.

* Для языка <tex> L_1 \cap L_2 :</tex>

полуразрешающая программа:

<tex>p(x)</tex>
'''if''' <tex> (p_1(x) == 1) \land (p_2(x) == 1) </tex>
'''return 1'''

* Для языка <tex> L_1 \times L_2 :</tex>

полуразрешающая программа:

<tex>p(\langle x, y \rangle)</tex>
'''if''' <tex> (p_1(x) == 1) \land (p_2(y) == 1) </tex>
'''return 1'''

* Для языка <tex> L_1^* :</tex>

полуразрешающая программа (по аналогии с <tex>L_1^*</tex> для разрешимого <tex>L_1</tex>):

<tex>p(x)</tex>
'''forall''' <tex>x_i :</tex> разбиение <tex>x</tex>
'''if''' <tex>(p_1(x_1) == 1) \land (p_1(x_2) == 1) \land \ ... \ \land (p_1(x_n) == 1)</tex>
'''return''' 1

Перечислитель же строится следующим образом: запускаем перечислитель для <tex> L_1 </tex> в цикле по тайм-лимиту и запоминаем выданные им слова. При выдаче каждого нового слова перебираем все возможные перестановки уже выданных слов и выдаем их.

* Для языка <tex> L_1 L_2 : </tex>

полуразрешающая программа:

<tex>p(x)</tex>
'''forall''' <tex>x_1, x_2 :</tex> разбиение <tex>x</tex>
'''if''' <tex>(p_1(x_1) == 1 \land p_2(x_2) == 1)</tex>
'''return''' 1

Перечислитель же для <tex> L_1 L_2 </tex> строим следующим образом: запускаем одновременно перечислители для <tex> L_1 </tex> и <tex> L_2 </tex>, запоминая все выданные слова. При выдаче новых слов перебираем все возможные пары из запомненных слов и выдаем их конкатенацию.
}}

{{Теорема
|statement=
Языки <tex> L_1, L_2 </tex> –- перечислимы, тогда следующие языки могут быть не перечислимы:

* Дополнение <tex>L_1\ (\overline{L_1})</tex>
* Разность <tex>L_1</tex> и <tex>L_2\ (L_1 \backslash L_2)</tex>

|proof=

Рассмотрим язык <tex> \overline{L_1} </tex>. Предположим, что он перечислим. Тогда имея какое-либо слово, мы можем одновременно запустить перечислители для <tex> L_1 </tex> и <tex> \overline{L_1} </tex>. В какой-то момент времени слово появится либо в выводе перечислителя для <tex> L_1 </tex>, либо в выводе перечислителя для <tex> \overline{L_1} </tex>. Тогда получится что <tex> L_1 </tex> разрешим, так как про любое слово мы можем узнать принадлежит оно <tex> L_1 </tex> или не принадлежит. Но мы знаем, что существуют перечислимые, но не разрешимые языки, следовательно, язык <tex> \overline{L_1} </tex> может быть не перечислим.

Теперь рассмотрим <tex> L_1 \backslash L_2 </tex>. В качестве <tex> L_1 </tex> возьмем язык, состоящий из всех слов. Тогда получится, что язык <tex> L_1 \backslash L_2 </tex> это <tex> \overline{L_2} </tex>. Про язык <tex> \overline{L_2} </tex> мы знаем, что он перечислим не всегда, следовательно и язык <tex> L_1 \backslash L_2 </tex> также не всегда перечислим.
}}

== Литература ==
* ''Верещагин Н. К., Шень А.'' '''Лекции по математической логике и теории алгоритов. Часть 3. Вычислимые функции''' — М.: МЦНМО, 1999

Обсуждение:Характеристика перечислимых множеств через вычислимые функции

2011-12-19T02:53:48Z

Roman Livarsky:

Характеристика перечислимых множеств через вычислимые функции

2011-12-19T02:50:19Z

Roman Livarsky:

{{Определение
|definition=Множество <tex>X</tex> называется перечислимым, если выполняется хотя бы одно условие из приведенных ниже:
# существует программа, перечисляющая все элементы <tex>X</tex> в произвольном порядке.
# <tex>X</tex> является областью определения [[Вычислимые функции|вычиcлимой функции]] <tex>f</tex>.
# <tex>X</tex> является областью значений [[Вычислимые функции|вычиcлимой функции]] <tex>f</tex>.
# Функция <tex>f_X(x) = \begin{cases}
1, & x \in X \\
\bot, & x \notin X
\end{cases}</tex> — вычислима.
}}

{{Теорема
|statement=
Определения ''1'', ''2'', ''3'', ''4'' эквивалентны.
|proof=
*1 <tex>\Rightarrow</tex> 4

Пусть <tex>p</tex> — программа, перечисляющая <tex>X</tex>.

Приведем программу <tex>q</tex>, вычисляющую функцию <tex>f_X(x):</tex>

<tex>q(x)</tex>
'''for''' <tex>k = 1 \ .. \ \infty</tex>
'''if''' <tex> p(k) == x </tex>
'''return''' 1

*2 <tex>\Rightarrow</tex> 1, 3 <tex>\Rightarrow</tex> 1

Пусть <tex>X</tex> — область определения [[Вычислимые функции|вычислимой функции]] <tex>f</tex>, вычисляемой программой <tex>p</tex>.

Введем обозначение: <tex>p(x)|_{TL}</tex>   —   остановить   <tex>p(x)</tex>   через   <tex>TL</tex>   секунд. Если   <tex>p(x)|_{TL}</tex>   за   <tex>TL</tex>   секунд так и не вернула значение функции <tex>f(x)</tex>, то возвращаем <tex>\bot</tex>.

Тогда <tex>X</tex> перечисляется такой программой:

<tex>q()</tex>
'''for''' <tex> TL = 1 \ .. \ \infty </tex>
'''for''' <tex> k = 1 \ ..\ TL</tex>
'''if''' <tex>p(k)|_{TL} \neq \bot </tex>
'''print'''<tex>(k)</tex>

Если print<tex>(k)</tex> заменить на print(<tex>p(k)|_{TL}</tex>), то <tex>q</tex> станет перечислять область значений <tex>f(x)</tex>.

*4 <tex>\Rightarrow</tex> 2, 4 <tex>\Rightarrow</tex> 3

Пусть дана <tex>f_X(x)</tex>.

Введем новую функцию <tex>g(x) = x</tex>, если <tex>f_X(x) \neq \bot</tex>.

Очевидно, она вычислима, и ее область определения и область значений совпадают с <tex>X</tex>.

}}

== Литература ==
* ''Верещагин Н. К., Шень А.'' '''Лекции по математической логике и теории алгоритов. Часть 3. Вычислимые функции''' — М.: МЦНМО, 1999

Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций

2011-12-19T02:35:08Z

Roman Livarsky:

{{Теорема
|statement=
Языки <tex> L_1, L_2 </tex> –- разрешимы, тогда языки

<tex>\left. \begin{array}{lll} L_1 \cup L_2 \\ L_1 \cap L_2 \\ \overline{L_1} \\ L_1 \backslash L_2 \\ L_1 \times L_2 \\L_1^* \\ L_1 L_2 \end{array} \right\} </tex> тоже разрешимы.
|proof=
Пусть <tex>p_1</tex> и <tex>p_2</tex> — разрешающие программы для языков
<tex>L_1</tex> и <tex>L_2</tex> соответственно. Для доказательства достаточно написать разрешающую программу (разрешитель) для каждого случая.

* Разрешающая программа для языка <tex> L_1 \cup L_2 :</tex>

<tex>p(x)</tex>
'''return''' <tex>(p_1(x) == 1) \lor (p_2(x) == 1)</tex>

* Для языка <tex> L_1 \cap L_2 :</tex>

<tex>p(x)</tex>
'''return''' <tex>(p_1(x) == 1) \land (p_2(x) == 1)</tex>

* Для языка <tex> \overline{L_1} :</tex>

<tex>p(x)</tex>
'''return''' <tex>(p_1(x) == 0)</tex>

* Для языка <tex> L_1 \backslash L_2 :</tex>

<tex>p(x)</tex>
'''return''' <tex>(p_1(x) == 1) \land (p_2(x) == 0)</tex>

* Для языка <tex> L_1 \times L_2 :</tex>

<tex>p(\langle x, y \rangle)</tex>
'''return''' <tex>(p_1(x) == 1) \land (p_2(y) == 1)</tex>

* Для языка <tex>L_1^* :</tex>

<tex>p(x)</tex>
'''forall''' <tex>x_i :</tex> разбиение <tex>x</tex>
'''if''' <tex>(p_1(x_1) == 1) \land (p_1(x_2) == 1) \land \ ... \ \land (p_1(x_n) == 1)</tex>
'''return''' 1
'''return''' 0

Разрешитель будет перебирать все возможные разбиения данного ему слова на подслова, и для каждого проверять принадлежность <tex> L_1 </tex>. Если хотя бы в одном разбиении все подслова будут принадлежать <tex> L_1 </tex>, то все слово принадлежит <tex> L_1^* </tex>, иначе — не принадлежит.

* Для языка <tex> L_1 L_2 : </tex>

<tex>p(x)</tex>
'''forall''' <tex>x_1, x_2 :</tex> разбиение <tex>x</tex>
'''if''' <tex>(p_1(x_1) == 1 \land p_2(x_2) == 1)</tex>
'''return''' 1
'''return''' 0

Разрешитель будет перебирать все возможные разбиения на два слова и проверять принадлежность первого слова <tex> L_1 </tex> и второго слова <tex> L_2 </tex>. Если хотя бы для одного разбиения оба разрешателя вернут 1, то слово принадлежит <tex> L_1 L_2 </tex>, иначе — не принадлежит.
}}

{{Теорема
|statement=
Языки <tex> L_1, L_2 </tex> –- перечислимы, тогда языки

<tex>\left. \begin{array}{lll} L_1 \cup L_2 \\ L_1 \cap L_2 \\ L_1 \times L_2\\ L_1^* \\ L_1 L_2 \end{array} \right\} </tex> тоже перечислимы.
|proof=

Пусть <tex>p_1</tex> и <tex>p_2</tex> — полуразрешающие программы для языков <tex>L_1</tex> и <tex>L_2</tex> соответственно. Для доказательства достаточно написать полуразрешающую или перечисляющую программу для каждого случая. Для некоторых языков предоставим оба варианта. Заметим, что <tex>p_1</tex> и <tex>p_2</tex> могут зависнуть при использовании в полуразрешающей программе для соответствующего языка, но это допустимо.

* Для языка <tex> L_1 \cup L_2 :</tex>

полуразрешающая программа:

<tex>p(x)</tex>
'''if''' <tex> (p_1(x) == 1) \lor (p_2(x) == 1) </tex>
'''return 1'''

Перечислитель же для этого языка будет по очереди на один шаг запускать перечислители для <tex>L_1</tex> и <tex>L_2</tex> и выдавать по очереди слова из <tex>L_1</tex> и <tex>L_2</tex> соответственно.

* Для языка <tex> L_1 \cap L_2 :</tex>

полуразрешающая программа:

<tex>p(x)</tex>
'''if''' <tex> (p_1(x) == 1) \land (p_2(x) == 1) </tex>
'''return 1'''

* Для языка <tex> L_1 \times L_2 :</tex>

полуразрешающая программа:

<tex>p(\langle x, y \rangle)</tex>
'''if''' <tex> (p_1(x) == 1) \land (p_2(y) == 1) </tex>
'''return 1'''

* Для языка <tex> L_1^* :</tex>

полуразрешающая программа (по аналогии с <tex>L_1^*</tex> для разрешимого <tex>L_1</tex>):

<tex>p(x)</tex>
'''forall''' <tex>x_i :</tex> разбиение <tex>x</tex>
'''if''' <tex>(p_1(x_1) == 1) \land (p_1(x_2) == 1) \land \ ... \ \land (p_1(x_n) == 1)</tex>
'''return''' 1

Перечислитель же строится следующим образом: запускаем перечислитель для <tex> L_1 </tex> в цикле по тайм-лимиту и запоминаем выданные им слова. При выдаче каждого нового слова перебираем все возможные перестановки уже выданных слов и выдаем их.

* Для языка <tex> L_1 L_2 : </tex>

полуразрешающая программа:

<tex>p(x)</tex>
'''forall''' <tex>x_1, x_2 :</tex> разбиение <tex>x</tex>
'''if''' <tex>(p_1(x_1) == 1 \land p_2(x_2) == 1)</tex>
'''return''' 1

Перечислитель же для <tex> L_1 L_2 </tex> строим следующим образом: запускаем одновременно перечислители для <tex> L_1 </tex> и <tex> L_2 </tex>, запоминая все выданные слова. При выдаче новых слов перебираем все возможные пары из запомненных слов и выдаем их конкатенацию.
}}

{{Теорема
|statement=
Языки <tex> L_1, L_2 </tex> –- перечислимы, тогда языки

<tex>\left. \begin{array}{lll} \overline{L_1} \\ L_1 \backslash L_2 \end{array} \right\} </tex> могут быть не перечислимы.

|proof=

Рассмотрим язык <tex> \overline{L_1} </tex>. Предположим, что он перечислим. Тогда имея какое-либо слово, мы можем одновременно запустить перечислители для <tex> L_1 </tex> и <tex> \overline{L_1} </tex>. В какой-то момент времени слово появится либо в выводе перечислителя для <tex> L_1 </tex>, либо в выводе перечислителя для <tex> \overline{L_1} </tex>. Тогда получится что <tex> L_1 </tex> разрешим, так как про любое слово мы можем узнать принадлежит оно <tex> L_1 </tex> или не принадлежит. Но мы знаем, что существуют перечислимые, но не разрешимые языки, следовательно, язык <tex> \overline{L_1} </tex> может быть не перечислим.

Теперь рассмотрим <tex> L_1 \backslash L_2 </tex>. В качестве <tex> L_1 </tex> возьмем язык, состоящий из всех слов. Тогда получится, что язык <tex> L_1 \backslash L_2 </tex> это <tex> \overline{L_2} </tex>. Про язык <tex> \overline{L_2} </tex> мы знаем, что он перечислим не всегда, следовательно и язык <tex> L_1 \backslash L_2 </tex> также не всегда перечислим.
}}

== Литература ==
* ''Верещагин Н. К., Шень А.'' '''Лекции по математической логике и теории алгоритов. Часть 3. Вычислимые функции''' — М.: МЦНМО, 1999

Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций

2011-12-19T02:32:19Z

Roman Livarsky:

{{Теорема
|statement=
Языки <tex> L_1, L_2 </tex> –- разрешимы, тогда языки

<tex>\left. \begin{array}{lll} L_1 \cup L_2 \\ L_1 \cap L_2 \\ \overline{L_1} \\ L_1 \backslash L_2 \\ L_1 \times L_2 \\L_1^* \\ L_1 L_2 \end{array} \right\} </tex> тоже разрешимы.
|proof=
Пусть <tex>p_1</tex> и <tex>p_2</tex> — разрешающие программы для языков
<tex>L_1</tex> и <tex>L_2</tex> соответственно. Для доказательства достаточно написать разрешающую программу (разрешитель) для каждого случая.

* Разрешающая программа для языка <tex> L_1 \cup L_2 :</tex>

<tex>p(x)</tex>
'''return''' <tex>(p_1(x) == 1) \lor (p_2(x) == 1)</tex>

* Для языка <tex> L_1 \cap L_2 :</tex>

<tex>p(x)</tex>
'''return''' <tex>(p_1(x) == 1) \land (p_2(x) == 1)</tex>

* Для языка <tex> \overline{L_1} :</tex>

<tex>p(x)</tex>
'''return''' <tex>(p_1(x) == 0)</tex>

* Для языка <tex> L_1 \backslash L_2 :</tex>

<tex>p(x)</tex>
'''return''' <tex>(p_1(x) == 1) \land (p_2(x) == 0)</tex>

* Для языка <tex> L_1 \times L_2 :</tex>

<tex>p(\langle x, y \rangle)</tex>
'''return''' <tex>(p_1(x) == 1) \land (p_2(y) == 1)</tex>

* Для языка <tex>L_1^* :</tex>

<tex>p(x)</tex>
'''forall''' <tex>x_i :</tex> разбиение <tex>x</tex>
'''if''' <tex>(p_1(x_1) == 1) \land (p_1(x_2) == 1) \land \ ... \ \land (p_1(x_n) == 1)</tex>
'''then return''' 1
'''return''' 0

Разрешитель будет перебирать все возможные разбиения данного ему слова на подслова, и для каждого проверять принадлежность <tex> L_1 </tex>. Если хотя бы в одном разбиении все подслова будут принадлежать <tex> L_1 </tex>, то все слово принадлежит <tex> L_1^* </tex>, иначе — не принадлежит.

* Для языка <tex> L_1 L_2 : </tex>

<tex>p(x)</tex>
'''forall''' <tex>x_1, x_2 :</tex> разбиение <tex>x</tex>
'''if''' <tex>(p_1(x_1) == 1 \land p_2(x_2) == 1)</tex>
'''then return''' 1
'''return''' 0

Разрешитель будет перебирать все возможные разбиения на два слова и проверять принадлежность первого слова <tex> L_1 </tex> и второго слова <tex> L_2 </tex>. Если хотя бы для одного разбиения оба разрешателя вернут 1, то слово принадлежит <tex> L_1 L_2 </tex>, иначе — не принадлежит.
}}

{{Теорема
|statement=
Языки <tex> L_1, L_2 </tex> –- перечислимы, тогда языки

<tex>\left. \begin{array}{lll} L_1 \cup L_2 \\ L_1 \cap L_2 \\ L_1 \times L_2\\ L_1^* \\ L_1 L_2 \end{array} \right\} </tex> тоже перечислимы.
|proof=

Пусть <tex>p_1</tex> и <tex>p_2</tex> — полуразрешающие программы для языков <tex>L_1</tex> и <tex>L_2</tex> соответственно. Для доказательства достаточно написать полуразрешающую или перечисляющую программу для каждого случая. Для некоторых языков предоставим оба варианта. Заметим, что <tex>p_1</tex> и <tex>p_2</tex> могут зависнуть при использовании в полуразрешающей программе для соответствующего языка, но это допустимо.

* Для языка <tex> L_1 \cup L_2 :</tex>

полуразрешающая программа:

<tex>p(x)</tex>
'''if''' <tex> (p_1(x) == 1) \lor (p_2(x) == 1) </tex>
'''then return 1'''

Перечислитель же для этого языка будет по очереди на один шаг запускать перечислители для <tex>L_1</tex> и <tex>L_2</tex> и выдавать по очереди слова из <tex>L_1</tex> и <tex>L_2</tex> соответственно.

* Для языка <tex> L_1 \cap L_2 :</tex>

полуразрешающая программа:

<tex>p(x)</tex>
'''if''' <tex> (p_1(x) == 1) \land (p_2(x) == 1) </tex>
'''then return 1'''

* Для языка <tex> L_1 \times L_2 :</tex>

полуразрешающая программа:

<tex>p(\langle x, y \rangle)</tex>
'''if''' <tex> (p_1(x) == 1) \land (p_2(y) == 1) </tex>
'''then return 1'''

* Для языка <tex> L_1^* :</tex>

полуразрешающая программа (по аналогии с <tex>L_1^*</tex> для разрешимого <tex>L_1</tex>):

<tex>p(x)</tex>
'''forall''' <tex>x_i :</tex> разбиение <tex>x</tex>
'''if''' <tex>(p_1(x_1) == 1) \land (p_1(x_2) == 1) \land \ ... \ \land (p_1(x_n) == 1)</tex>
'''then return''' 1

Перечислитель строится следующим образом: запускаем перечислитель для <tex> L_1 </tex> в цикле по тайм-лимиту и запоминаем выданные им слова. При выдаче каждого нового слова перебираем все возможные перестановки уже выданных слов и выдаем их.

* Для языка <tex> L_1 L_2 : </tex>

полуразрешающая программа:

<tex>p(x)</tex>
'''forall''' <tex>x_1, x_2 :</tex> разбиение <tex>x</tex>
'''if''' <tex>(p_1(x_1) == 1 \land p_2(x_2) == 1)</tex>
'''then return''' 1

Перечислитель для <tex> L_1 L_2 </tex> строим следующим образом: запускаем одновременно перечислители для <tex> L_1 </tex> и <tex> L_2 </tex>, запоминая все выданные слова. При выдаче новых слов перебираем все возможные пары из запомненных слов и выдаем их конкатенацию.
}}

{{Теорема
|statement=
Языки <tex> L_1, L_2 </tex> –- перечислимы, тогда языки

<tex>\left. \begin{array}{lll} \overline{L_1} \\ L_1 \backslash L_2 \end{array} \right\} </tex> могут быть не перечислимы.

|proof=

Рассмотрим язык <tex> \overline{L_1} </tex>. Предположим, что он перечислим. Тогда имея какое-либо слово, мы можем одновременно запустить перечислители для <tex> L_1 </tex> и <tex> \overline{L_1} </tex>. В какой-то момент времени слово появится либо в выводе перечислителя для <tex> L_1 </tex>, либо в выводе перечислителя для <tex> \overline{L_1} </tex>. Тогда получится что <tex> L_1 </tex> разрешим, так как про любое слово мы можем узнать принадлежит оно <tex> L_1 </tex> или не принадлежит. Но мы знаем, что существуют перечислимые, но не разрешимые языки, следовательно, язык <tex> \overline{L_1} </tex> может быть не перечислим.

Теперь рассмотрим <tex> L_1 \backslash L_2 </tex>. В качестве <tex> L_1 </tex> возьмем язык, состоящий из всех слов. Тогда получится, что язык <tex> L_1 \backslash L_2 </tex> это <tex> \overline{L_2} </tex>. Про язык <tex> \overline{L_2} </tex> мы знаем, что он перечислим не всегда, следовательно и язык <tex> L_1 \backslash L_2 </tex> также не всегда перечислим.
}}

== Литература ==
* ''Верещагин Н. К., Шень А.'' '''Лекции по математической логике и теории алгоритов. Часть 3. Вычислимые функции''' — М.: МЦНМО, 1999

Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций

2011-12-19T02:31:52Z

Roman Livarsky:

{{Теорема
|statement=
Языки <tex> L_1, L_2 </tex> –- разрешимы, тогда языки

<tex>\left. \begin{array}{lll} L_1 \cup L_2 \\ L_1 \cap L_2 \\ \overline{L_1} \\ L_1 \backslash L_2 \\ L_1 \times L_2 \\L_1^* \\ L_1 L_2 \end{array} \right\} </tex> тоже разрешимы.
|proof=
Пусть <tex>p_1</tex> и <tex>p_2</tex> — разрешающие программы для языков
<tex>L_1</tex> и <tex>L_2</tex> соответственно. Для доказательства достаточно написать разрешающую программу (разрешитель) для каждого случая.

* Разрешающая программа для языка <tex> L_1 \cup L_2 :</tex>

<tex>p(x)</tex>
'''return''' <tex>(p_1(x) == 1) \lor (p_2(x) == 1)</tex>

* Для языка <tex> L_1 \cap L_2 :</tex>

<tex>p(x)</tex>
'''return''' <tex>(p_1(x) == 1) \land (p_2(x) == 1)</tex>

* Для языка <tex> \overline{L_1} :</tex>

<tex>p(x)</tex>
'''return''' <tex>(p_1(x) == 0)</tex>

* Для языка <tex> L_1 \backslash L_2 :</tex>

<tex>p(x)</tex>
'''return''' <tex>(p_1(x) == 1) \land (p_2(x) == 0)</tex>

* Для языка <tex> L_1 \times L_2 :</tex>

<tex>p(\langle x, y \rangle)</tex>
'''return''' <tex>(p_1(x) == 1) \land (p_2(y) == 1)</tex>

* Для языка <tex>L_1^* :</tex>

<tex>p(x)</tex>
'''forall''' <tex>x_i :</tex> разбиение <tex>x</tex>
'''if''' <tex>(p_1(x_1) == 1) \land (p_1(x_2) == 1) \land \ ... \ \land (p_1(x_n) == 1)</tex>
'''then return''' 1
'''return''' 0

Разрешитель будет перебирать все возможные разбиения данного ему слова на подслова, и для каждого проверять принадлежность <tex> L_1 </tex>. Если хотя бы в одном разбиении все подслова будут принадлежать <tex> L_1 </tex>, то все слово принадлежит <tex> L_1^* </tex>, иначе — не принадлежит.

* Для языка <tex> L_1 L_2 : </tex>

<tex>p(x)</tex>
'''forall''' <tex>x_1, x_2 :</tex> разбиение <tex>x</tex>
'''if''' <tex>(p_1(x_1) == 1 \land p_2(x_2) == 1)</tex>
'''then return''' 1
'''return''' 0

Разрешитель будет перебирать все возможные разбиения на два слова и проверять принадлежность первого слова <tex> L_1 </tex> и второго слова <tex> L_2 </tex>. Если хотя бы для одного разбиения оба разрешателя вернут 1, то слово принадлежит <tex> L_1 L_2 </tex>, иначе — не принадлежит.
}}

{{Теорема
|statement=
Языки <tex> L_1, L_2 </tex> –- перечислимы, тогда языки

<tex>\left. \begin{array}{lll} L_1 \cup L_2 \\ L_1 \cap L_2 \\ L_1 \times L_2\\ L_1^* \\ L_1 L_2 \end{array} \right\} </tex> тоже перечислимы.
|proof=

Пусть <tex>p_1</tex> и <tex>p_2</tex> — полуразрешающие программы для языков <tex>L_1</tex> и <tex>L_2</tex> соответственно. Для доказательства достаточно написать полуразрешающую или перечисляющую программу для каждого случая. Для некоторых языков предоставим оба варианта. Заметим, что <tex>p_1</tex> и <tex>p_2</tex> могут зависнуть при использовании в полуразрешающей программе для соответствующего языка, но это допустимо.

* Для языка <tex> L_1 \cup L_2 :</tex>

полуразрешающая программа:

<tex>p(x)</tex>
'''if''' <tex> (p_1(x) == 1) \lor (p_2(x) == 1) </tex>
'''then return 1'''

Перечислитель же для этого языка будет по очереди на один шаг запускать перечислители для <tex>L_1</tex> и <tex>L_2</tex> и выдавать по очереди слова из <tex>L_1</tex> и <tex>L_2</tex> соответственно.

* Для языка <tex> L_1 \cap L_2 :</tex>

полуразрешающая программа:

<tex>p(x)</tex>
'''if''' <tex> (p_1(x) == 1) \land (p_2(x) == 1) </tex>
'''then return 1'''

* Для языка <tex> L_1 \times L_2 :</tex>

полуразрешающая программа:

<tex>p(\langle x, y \rangle)</tex>
'''if''' <tex> (p_1(x) == 1) \land (p_2(y) == 1) </tex>
'''then return 1'''

* Для языка <tex> L_1^* :</tex>

полуразрешающая программа (по аналогии с <tex>L_1^*</tex> для разрешимого <tex>L_1</tex>):

<tex>p(x)</tex>
'''forall''' <tex>x_i :</tex> разбиение <tex>x</tex>
'''if''' <tex>(p_1(x_1) == 1) \land (p_1(x_2) == 1) \land \ ... \ \land (p_1(x_n) == 1)</tex>
'''then return''' 1

Перечислитель строится следующим образом: запускаем перечислитель для <tex> L_1 </tex> в цикле по тайм-лимиту и запоминаем выданные им слова. При выдаче каждого нового слова перебираем все возможные перестановки уже выданных слов и выдаем их.

* Для языка <tex> L_1 L_2 : </tex>

полуразрешающая программа:

<tex>p(x)</tex>
'''forall''' <tex>x_1, x_2 :</tex> разбиение <tex>x</tex>
'''if''' <tex>(p_1(x_1) == 1 \land p_2(x_2) == 1)</tex>
'''then return''' 1

Перечислитель для <tex> L_1 L_2 </tex> строим следующим образом: запускаем одновременно перечислители для <tex> L_1 </tex> и <tex> L_2 </tex>, запоминая все выданные слова. При выдаче новых слов перебираем все возможные пары из запомненных слов и выдаем их конкатенацию.
}}

{{Теорема
|statement=
Языки <tex> L_1, L_2 </tex> –- перечислимы, тогда языки

<tex>\left. \begin{array}{lll} \overline{L_1} \\ L_1 \backslash L_2 \end{array} \right\} </tex> могут быть не перечислимы.

|proof=

Рассмотрим язык <tex> \overline{L_1} </tex>. Предположим, что он перечислим. Тогда имея какое-либо слово, мы можем одновременно запустить перечислители для <tex> L_1 </tex> и <tex> \overline{L_1} </tex>. В какой-то момент времени слово появится либо в выводе перечислителя для <tex> L_1 </tex>, либо в выводе перечислителя для <tex> \overline{L_1} </tex>. Тогда получится что <tex> L_1 </tex> разрешим, так как про любое слово мы можем узнать принадлежит оно <tex> L_1 </tex> или не принадлежит. Но мы знаем, что существуют перечислимые, но не разрешимые языки, следовательно, язык <tex> \overline{L_1} </tex> может быть не перечислим.

Теперь рассмотрим <tex> L_1 \backslash L_2 </tex>. В качестве <tex> L_1 </tex> возьмем язык, состоящий из всех слов. Тогда получится, что язык <tex> L_1 \backslash L_2 </tex> это <tex> \overline{L_2} </tex>. Про язык <tex> \overline{L_2} </tex> мы знаем, что он перечислим не всегда, следовательно и язык <tex> L_1 \backslash L_2 </tex> также не всегда перечислим.
}}

== Литература ==
* ''Верещагин Н. К., Шень А.'' '''Лекции по математической логике и теории алгоритов. Часть 3. Вычислимые функции''' -- М.: МЦНМО, 1999

Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций

2011-12-19T02:31:21Z

Roman Livarsky:

{{Теорема
|statement=
Языки <tex> L_1, L_2 </tex> –- разрешимы, тогда языки

<tex>\left. \begin{array}{lll} L_1 \cup L_2 \\ L_1 \cap L_2 \\ \overline{L_1} \\ L_1 \backslash L_2 \\ L_1 \times L_2 \\L_1^* \\ L_1 L_2 \end{array} \right\} </tex> тоже разрешимы.
|proof=
Пусть <tex>p_1</tex> и <tex>p_2</tex> — разрешающие программы для языков
<tex>L_1</tex> и <tex>L_2</tex> соответственно. Для доказательства достаточно написать разрешающую программу (разрешатель) для каждого случая.

* Разрешающая программа для языка <tex> L_1 \cup L_2 :</tex>

<tex>p(x)</tex>
'''return''' <tex>(p_1(x) == 1) \lor (p_2(x) == 1)</tex>

* Для языка <tex> L_1 \cap L_2 :</tex>

<tex>p(x)</tex>
'''return''' <tex>(p_1(x) == 1) \land (p_2(x) == 1)</tex>

* Для языка <tex> \overline{L_1} :</tex>

<tex>p(x)</tex>
'''return''' <tex>(p_1(x) == 0)</tex>

* Для языка <tex> L_1 \backslash L_2 :</tex>

<tex>p(x)</tex>
'''return''' <tex>(p_1(x) == 1) \land (p_2(x) == 0)</tex>

* Для языка <tex> L_1 \times L_2 :</tex>

<tex>p(\langle x, y \rangle)</tex>
'''return''' <tex>(p_1(x) == 1) \land (p_2(y) == 1)</tex>

* Для языка <tex>L_1^* :</tex>

<tex>p(x)</tex>
'''for''' <tex>x_i :</tex> разбиение <tex>x</tex>
'''if''' <tex>(p_1(x_i) == 1)</tex>
'''then return''' 1
'''return''' 0

Разрешатель будет перебирать все возможные разбиения данного ему слова на подслова, и для каждого проверять принадлежность <tex> L_1 </tex>. Если хотя бы в одном разбиении все подслова будут принадлежать <tex> L_1 </tex>, то все слово принадлежит <tex> L_1^* </tex>, иначе — не принадлежит.

* Для языка <tex> L_1 L_2 : </tex>

<tex>p(x)</tex>
'''for''' <tex>x_1, x_2 :</tex> разбиение <tex>x</tex>
'''if''' <tex>(p_1(x_1) == 1 \land p_2(x_2) == 1)</tex>
'''then return''' 1
'''return''' 0

Разрешатель будет перебирать все возможные разбиения на два слова и проверять принадлежность первого слова <tex> L_1 </tex> и второго слова <tex> L_2 </tex>. Если хотя бы для одного разбиения оба разрешателя вернут 1, то слово принадлежит <tex> L_1 L_2 </tex>, иначе — не принадлежит.
}}

{{Теорема
|statement=
Языки <tex> L_1, L_2 </tex> –- перечислимы, тогда языки

<tex>\left. \begin{array}{lll} L_1 \cup L_2 \\ L_1 \cap L_2 \\ L_1 \times L_2\\ L_1^* \\ L_1 L_2 \end{array} \right\} </tex> тоже перечислимы.
|proof=

Пусть <tex>p_1</tex> и <tex>p_2</tex> — полуразрешающие программы для языков <tex>L_1</tex> и <tex>L_2</tex> соответственно. Для доказательства достаточно написать полуразрешающую или перечисляющую программу для каждого случая. Заметим, что <tex>p_1</tex> и <tex>p_2</tex> могут зависнуть при использовании в полуразрешающей программе для соответствующего языка, но это допустимо.

* Для языка <tex> L_1 \cup L_2 :</tex>

полуразрешающая программа:

<tex>p(x)</tex>
'''for''' <tex>k = 1\ .. \ \infty </tex>
'''if''' <tex> (p_1|_k(x) == 1) \lor (p_2|_k(x) == 1) </tex>
'''then return 1'''

Перечислитель же для этого языка будет по очереди на один шаг запускать перечислители для <tex>L_1</tex> и <tex>L_2</tex> и выдавать по очереди слова из <tex>L_1</tex> и <tex>L_2</tex> соответственно.

* Для языка <tex> L_1 \cap L_2 :</tex>

полуразрешающая программа:

<tex>p(x)</tex>
'''for''' <tex>k = 1\ .. \ \infty </tex>
'''if''' <tex> (p_1|_k(x) == 1) \land (p_2|_k(x) == 1) </tex>
'''then return 1'''

* Для языка <tex> L_1 \times L_2 :</tex>

полуразрешающая программа:

<tex>p(\langle x, y \rangle)</tex>
'''for''' <tex>k = 1\ .. \ \infty </tex>
'''if''' <tex> (p_1|_k(x) == 1) \land (p_2|_k(y) == 1) </tex>
'''then return 1'''

* Для языка <tex> L_1^* :</tex>

полуразрешающая программа (по аналогии с <tex>L_1^*</tex> для разрешимого <tex>L_1</tex>):

<tex>p(x)</tex>
'''for''' <tex>x_i :</tex> разбиение <tex>x</tex>
'''if''' <tex>(p_1(x_i) == 1)</tex>
'''then return''' 1

Перечислитель строится следующим образом: запускаем перечислитель для <tex> L_1 </tex> в цикле по тайм-лимиту и запоминаем выданные им слова. При выдаче каждого нового слова перебираем все возможные перестановки уже выданных слов и выдаем их.

* Для языка <tex> L_1 L_2 : </tex>

полуразрешающая программа:

<tex>p(x)</tex>
'''for''' <tex>x_1, x_2 :</tex> разбиение <tex>x</tex>
'''if''' <tex>(p_1(x_1) == 1 \land p_2(x_2) == 1)</tex>
'''then return''' 1

Перечислитель для <tex> L_1 L_2 </tex> строим следующим образом: запускаем одновременно перечислители для <tex> L_1 </tex> и <tex> L_2 </tex>, запоминая все выданные слова. При выдаче новых слов перебираем все возможные пары из запомненных слов и выдаем их конкатенацию.
}}

{{Теорема
|statement=
Языки <tex> L_1, L_2 </tex> –- перечислимы, тогда языки

<tex>\left. \begin{array}{lll} \overline{L_1} \\ L_1 \backslash L_2 \end{array} \right\} </tex> могут быть не перечислимы.

|proof=

Рассмотрим язык <tex> \overline{L_1} </tex>. Предположим, что он перечислим. Тогда имея какое-либо слово, мы можем одновременно запустить перечислители для <tex> L_1 </tex> и <tex> \overline{L_1} </tex>. В какой-то момент времени слово появится либо в выводе перечислителя для <tex> L_1 </tex>, либо в выводе перечислителя для <tex> \overline{L_1} </tex>. Тогда получится что <tex> L_1 </tex> разрешим, так как про любое слово мы можем узнать принадлежит оно <tex> L_1 </tex> или не принадлежит. Но мы знаем, что существуют перечислимые, но не разрешимые языки, следовательно, язык <tex> \overline{L_1} </tex> может быть не перечислим.

Теперь рассмотрим <tex> L_1 \backslash L_2 </tex>. В качестве <tex> L_1 </tex> возьмем язык, состоящий из всех слов. Тогда получится, что язык <tex> L_1 \backslash L_2 </tex> это <tex> \overline{L_2} </tex>. Про язык <tex> \overline{L_2} </tex> мы знаем, что он перечислим не всегда, следовательно и язык <tex> L_1 \backslash L_2 </tex> также не всегда перечислим.
}}

== Литература ==
* ''Верещагин Н. К., Шень А.'' '''Лекции по математической логике и теории алгоритов. Часть 3. Вычислимые функции''' — М.: МЦНМО, 1999

Характеристика перечислимых множеств через вычислимые функции

2011-12-19T02:29:46Z

Roman Livarsky:

{{Определение
|definition=Множество <tex>X</tex> называется перечислимым, если выполняется хотя бы одно условие из приведенных ниже:
# существует программа, перечисляющая все элементы <tex>X</tex> в произвольном порядке.
# <tex>X</tex> является областью определения [[Вычислимые функции|вычиcлимой функции]] <tex>f</tex>.
# <tex>X</tex> является областью значений [[Вычислимые функции|вычиcлимой функции]] <tex>f</tex>.
# функция <tex>f_X(x) = \begin{cases}
1, & x \in X \\
\bot, & x \notin X
\end{cases}</tex> — вычислима.
}}

{{Теорема
|statement=
Определения ''1'', ''2'', ''3'', ''4'' эквивалентны.
|proof=
*1 <tex>\Rightarrow</tex> 4

Пусть <tex>p</tex> — программа, перечисляющая <tex>X</tex>.

Приведем программу <tex>q</tex>, вычисляющую функцию <tex>f_X(x):</tex>

<tex>q(x)</tex>
'''for''' <tex>k = 1 \ .. \ \infty</tex>
'''if''' <tex> p(k) == x </tex>
'''return''' 1

*2 <tex>\Rightarrow</tex> 1, 3 <tex>\Rightarrow</tex> 1

Пусть <tex>X</tex> — область определения [[Вычислимые функции|вычислимой функции]] <tex>f</tex>, вычисляемой программой <tex>p</tex>.

Тогда <tex>X</tex> перечисляется такой программой:

<tex>q()</tex>
'''for''' <tex> TL = 1 \ .. \ \infty </tex>
'''for''' <tex> k = 1 \ ..\ TL</tex>
'''if''' <tex>p(k)|_{TL} \neq \bot </tex>
'''print'''<tex>(k)</tex>

Если print<tex>(k)</tex> заменить на print(<tex>p(k)|_{TL}</tex>), то <tex>q</tex> станет перечислять область значений <tex>f(x)</tex>.

*4 <tex>\Rightarrow</tex> 2, 4 <tex>\Rightarrow</tex> 3

Пусть дана <tex>f_X(x)</tex>.

Введем новую функцию <tex>g(x) = x</tex>, если <tex>f_X(x) \neq \bot</tex>.

Очевидно, она вычислима, и ее область определения и область значений совпадают с <tex>X</tex>.

}}

== Литература ==
* ''Верещагин Н. К., Шень А.'' '''Лекции по математической логике и теории алгоритов. Часть 3. Вычислимые функции''' — М.: МЦНМО, 1999

Характеристика перечислимых множеств через вычислимые функции

2011-12-19T02:26:02Z

Roman Livarsky:

{{Определение
|definition=Множество <tex>X</tex> называется перечислимым, если выполняется хотя бы одно условие из приведенных ниже:
# существует программа, перечисляющая все элементы <tex>X</tex> в произвольном порядке.
# <tex>X</tex> является областью определения вычиcлимой функции <tex>f</tex>.
# <tex>X</tex> является областью значений вычиcлимой функции <tex>f</tex>.
# функция <tex>f_X(x) = \begin{cases}
1, & x \in X \\
\bot, & x \notin X
\end{cases}</tex> — вычислима.
}}

{{Теорема
|statement=
Определения ''1'', ''2'', ''3'', ''4'' эквивалентны.
|proof=
*1 <tex>\Rightarrow</tex> 4

Пусть <tex>p</tex> — программа, перечисляющая <tex>X</tex>.

Приведем программу <tex>q</tex>, вычисляющую функцию <tex>f_X(x):</tex>

<tex>q(x)</tex>
'''for''' <tex>k = 1 \ .. \ \infty</tex>
'''if''' <tex> p(k) == x </tex>
'''return''' 1

*2 <tex>\Rightarrow</tex> 1, 3 <tex>\Rightarrow</tex> 1

Пусть <tex>X</tex> — область определения вычислимой функции <tex>f</tex>, вычисляемой программой <tex>p</tex>.

Тогда <tex>X</tex> перечисляется такой программой:

<tex>q()</tex>
'''for''' <tex> TL = 1 \ .. \ \infty </tex>
'''for''' <tex> k = 1 \ ..\ TL</tex>
'''if''' <tex>p(k)|_{TL} \neq \bot </tex>
'''print'''<tex>(k)</tex>

Если print<tex>(k)</tex> заменить на print(<tex>p(k)|_{TL}</tex>), то <tex>q</tex> станет перечислять область значений <tex>f(x)</tex>.

*4 <tex>\Rightarrow</tex> 2, 4 <tex>\Rightarrow</tex> 3

Пусть дана <tex>f_X(x)</tex>.

Введем новую функцию <tex>g(x) = x</tex>, если <tex>f_X(x) \neq \bot</tex>.

Очевидно, она вычислима, и ее область определения и область значений совпадают с <tex>X</tex>.

}}

== Литература ==
* ''Верещагин Н. К., Шень А.'' '''Лекции по математической логике и теории алгоритов. Часть 3. Вычислимые функции''' — М.: МЦНМО, 1999

Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций

2011-12-18T06:52:15Z

Roman Livarsky:

{{Теорема
|statement=
Языки <tex> L_1, L_2 </tex> –- разрешимы, тогда языки

<tex>\left. \begin{array}{lll} L_1 \cup L_2 \\ L_1 \cap L_2 \\ \overline{L_1} \\ L_1 \backslash L_2 \\ L_1 \times L_2 \\L_1^* \\ L_1 L_2 \end{array} \right\} </tex> тоже разрешимы.
|proof=
Пусть <tex>p_1</tex> и <tex>p_2</tex> — разрешающие программы для языков
<tex>L_1</tex> и <tex>L_2</tex> соответственно. Для доказательства достаточно написать разрешающую программу (разрешатель) для каждого случая.

* Разрешающая программа для языка <tex> L_1 \cup L_2 :</tex>

<tex>p(x)</tex>
'''return''' <tex>(p_1(x) == 1) \lor (p_2(x) == 1)</tex>

* Для языка <tex> L_1 \cap L_2 :</tex>

<tex>p(x)</tex>
'''return''' <tex>(p_1(x) == 1) \land (p_2(x) == 1)</tex>

* Для языка <tex> \overline{L_1} :</tex>

<tex>p(x)</tex>
'''return''' <tex>(p_1(x) == 0)</tex>

* Для языка <tex> L_1 \backslash L_2 :</tex>

<tex>p(x)</tex>
'''return''' <tex>(p_1(x) == 1) \land (p_2(x) == 0)</tex>

* Для языка <tex> L_1 \times L_2 :</tex>

<tex>p(\langle x, y \rangle)</tex>
'''return''' <tex>(p_1(x) == 1) \land (p_2(y) == 1)</tex>

* Для языка <tex>L_1^* :</tex>

<tex>p(x)</tex>
'''for''' <tex>x_i :</tex> разбиение <tex>x</tex>
'''if''' <tex>(p_1(x_i) == 1)</tex>
'''then return''' 1
'''return''' 0

Разрешатель будет перебирать все возможные разбиения данного ему слова на подслова, и для каждого проверять принадлежность <tex> L_1 </tex>. Если хотя бы в одном разбиении все подслова будут принадлежать <tex> L_1 </tex>, то все слово принадлежит <tex> L_1^* </tex>, иначе — не принадлежит.

* Для языка <tex> L_1 L_2 : </tex>

<tex>p(x)</tex>
'''for''' <tex>x_1, x_2 :</tex> разбиение <tex>x</tex>
'''if''' <tex>(p_1(x_1) == 1 \land p_2(x_2) == 1)</tex>
'''then return''' 1
'''return''' 0

Разрешатель будет перебирать все возможные разбиения на два слова и проверять принадлежность первого слова <tex> L_1 </tex> и второго слова <tex> L_2 </tex>. Если хотя бы для одного разбиения оба разрешателя вернут 1, то слово принадлежит <tex> L_1 L_2 </tex>, иначе — не принадлежит.
}}

{{Теорема
|statement=
Языки <tex> L_1, L_2 </tex> –- перечислимы, тогда языки

<tex>\left. \begin{array}{lll} L_1 \cup L_2 \\ L_1 \cap L_2 \\ L_1 \times L_2\\ L_1^* \\ L_1 L_2 \end{array} \right\} </tex> тоже перечислимы.
|proof=

Пусть <tex>p_1</tex> и <tex>p_2</tex> — полуразрешающие программы для языков <tex>L_1</tex> и <tex>L_2</tex> соответственно. Для доказательства достаточно написать полуразрешающую или перечисляющую программу для каждого случая. Заметим, что <tex>p_1</tex> и <tex>p_2</tex> могут зависнуть при использовании в полуразрешающей программе для соответствующего языка, но это допустимо.

* Для языка <tex> L_1 \cup L_2 :</tex>

полуразрешающая программа:

<tex>p(x)</tex>
'''for''' <tex>k = 1\ .. \ \infty </tex>
'''if''' <tex> (p_1|_k(x) == 1) \lor (p_2|_k(x) == 1) </tex>
'''then return 1'''

Перечислитель же для этого языка будет по очереди на один шаг запускать перечислители для <tex>L_1</tex> и <tex>L_2</tex> и выдавать по очереди слова из <tex>L_1</tex> и <tex>L_2</tex> соответственно.

* Для языка <tex> L_1 \cap L_2 :</tex>

полуразрешающая программа:

<tex>p(x)</tex>
'''for''' <tex>k = 1\ .. \ \infty </tex>
'''if''' <tex> (p_1|_k(x) == 1) \land (p_2|_k(x) == 1) </tex>
'''then return 1'''

* Для языка <tex> L_1 \times L_2 :</tex>

полуразрешающая программа:

<tex>p(\langle x, y \rangle)</tex>
'''for''' <tex>k = 1\ .. \ \infty </tex>
'''if''' <tex> (p_1|_k(x) == 1) \land (p_2|_k(y) == 1) </tex>
'''then return 1'''

* Для языка <tex> L_1^* :</tex>

полуразрешающая программа (по аналогии с <tex>L_1^*</tex> для разрешимого <tex>L_1</tex>):

<tex>p(x)</tex>
'''for''' <tex>x_i :</tex> разбиение <tex>x</tex>
'''if''' <tex>(p_1(x_i) == 1)</tex>
'''then return''' 1

Перечислитель строится следующим образом: запускаем перечислитель для <tex> L_1 </tex> в цикле по тайм-лимиту и запоминаем выданные им слова. При выдаче каждого нового слова перебираем все возможные перестановки уже выданных слов и выдаем их.

* Для языка <tex> L_1 L_2 : </tex>

полуразрешающая программа:

<tex>p(x)</tex>
'''for''' <tex>x_1, x_2 :</tex> разбиение <tex>x</tex>
'''if''' <tex>(p_1(x_1) == 1 \land p_2(x_2) == 1)</tex>
'''then return''' 1

Перечислитель для <tex> L_1 L_2 </tex> строим следующим образом: запускаем одновременно перечислители для <tex> L_1 </tex> и <tex> L_2 </tex>, запоминая все выданные слова. При выдаче новых слов перебираем все возможные пары из запомненных слов и выдаем их конкатенацию.
}}

{{Теорема
|statement=
Языки <tex> L_1, L_2 </tex> –- перечислимы, тогда языки

<tex>\left. \begin{array}{lll} \overline{L_1} \\ L_1 \backslash L_2 \end{array} \right\} </tex> могут быть не перечислимы.

|proof=

Рассмотрим язык <tex> \overline{L_1} </tex>. Предположим, что он перечислим. Тогда имея какое-либо слово, мы можем одновременно запустить перечислители для <tex> L_1 </tex> и <tex> \overline{L_1} </tex>. В какой-то момент времени слово появится либо в выводе перечислителя для <tex> L_1 </tex>, либо в выводе перечислителя для <tex> \overline{L_1} </tex>. Тогда получится что <tex> L_1 </tex> разрешим, так как про любое слово мы можем узнать принадлежит оно <tex> L_1 </tex> или не принадлежит. Но мы знаем, что существуют перечислимые, но не разрешимые языки, следовательно, язык <tex> \overline{L_1} </tex> может быть не перечислим.

Теперь рассмотрим <tex> L_1 \backslash L_2 </tex>. В качестве <tex> L_1 </tex> возьмем язык, состоящий из всех слов. Тогда получится, что язык <tex> L_1 \backslash L_2 </tex> это <tex> \overline{L_2} </tex>. Про язык <tex> \overline{L_2} </tex> мы знаем, что он перечислим не всегда, следовательно и язык <tex> L_1 \backslash L_2 </tex> также не всегда перечислим.
}}

== Литература ==
* ''Верещагин Н. К., Шень А.'' '''Лекции по математической логике и теории алгоритов. Часть 3. Вычислимые функции''' -- М.: МЦНМО, 1999

Характеристика перечислимых множеств через вычислимые функции

2011-12-18T06:51:44Z

Roman Livarsky:

{{Определение
|definition=Множество <tex>X</tex> называется перечислимым, если выполняется хотя бы одно условие из приведенных ниже:
# Существует программа перечисляющая все элементы <tex>X</tex> в произвольном порядке.
# <tex>X</tex> является областью определения вычиcлимой функции <tex>f</tex>.
# <tex>X</tex> является областью значений вычиcлимой функции <tex>f</tex>.
# Функция <tex>f_X(x) = \begin{cases}
1, & x \in X \\
\bot, & x \notin X
\end{cases}</tex> — вычислима.
}}

{{Теорема
|statement=
Определения ''1'', ''2'', ''3'', ''4'' эквивалентны.
|proof=
*1 <tex>\Rightarrow</tex> 4

Пусть <tex>p</tex> — программа, перечисляющая <tex>X</tex>.

Приведем программу <tex>q</tex>, вычисляющую функцию <tex>f_X(x):</tex>

<tex>q(x)</tex>
'''for''' <tex>k = 1 \ .. \ \infty</tex>
'''if''' <tex> p(k) == x </tex>
'''then return''' 1

*2 <tex>\Rightarrow</tex> 1, 3 <tex>\Rightarrow</tex> 1

Пусть <tex>X</tex> — область определения вычислимой функции <tex>f</tex>, вычисляемой программой <tex>p</tex>.

Введем обозначение: <tex>p(x)|_{TL}</tex>   —   запустить   <tex>p(x)</tex>   на   <tex>TL</tex>   секунд. Если   <tex>p(x)|_{TL}</tex>   за   <tex>TL</tex>   секунд так и не вернула значение функции <tex>f(x)</tex>, то возвращаем <tex>\bot</tex>.

Тогда <tex>X</tex> перечисляется такой программой:

<tex>q()</tex>
'''for''' <tex> TL = 1 \ .. \ \infty </tex>
'''for''' <tex> k = 1 \ ..\ TL</tex>
'''if''' <tex>p(k)|_{TL} \neq \bot </tex>
'''then print'''<tex>(k)</tex>

Если print<tex>(k)</tex> заменить на print(<tex>p(k)|_{TL}</tex>), то <tex>q</tex> станет перечислять область значений <tex>f(x)</tex>.

*4 <tex>\Rightarrow</tex> 2, 4 <tex>\Rightarrow</tex> 3

Пусть дана <tex>f_X(x)</tex>.

Введем новую функцию <tex>g(x) = x</tex>, если <tex>f_X(x) \neq \bot</tex>.

Очевидно, она вычислима, и ее область определения и область значений совпадают с <tex>X</tex>.

}}

== Литература ==
* ''Верещагин Н. К., Шень А.'' '''Лекции по математической логике и теории алгоритов. Часть 3. Вычислимые функции''' -- М.: МЦНМО, 1999

Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций

2011-12-18T06:11:36Z

Roman Livarsky:

{{Теорема
|statement=
Языки <tex> L_1, L_2 </tex> –- разрешимы, тогда языки

<tex>\left. \begin{array}{lll} L_1 \cup L_2 \\ L_1 \cap L_2 \\ \overline{L_1} \\ L_1 \backslash L_2 \\ L_1 \times L_2 \\L_1^* \\ L_1 L_2 \end{array} \right\} </tex> тоже разрешимы.
|proof=
Пусть <tex>p_1</tex> и <tex>p_2</tex> — разрешающие программы для языков
<tex>L_1</tex> и <tex>L_2</tex> соответственно. Для доказательства достаточно написать разрешающую программу (разрешатель) для каждого случая.

* Разрешающая программа для языка <tex> L_1 \cup L_2 :</tex>

<tex>p(x)</tex>
'''return''' <tex>(p_1(x) == 1) \lor (p_2(x) == 1)</tex>

* Для языка <tex> L_1 \cap L_2 :</tex>

<tex>p(x)</tex>
'''return''' <tex>(p_1(x) == 1) \land (p_2(x) == 1)</tex>

* Для языка <tex> \overline{L_1} :</tex>

<tex>p(x)</tex>
'''return''' <tex>(p_1(x) == 0)</tex>

* Для языка <tex> L_1 \backslash L_2 :</tex>

<tex>p(x)</tex>
'''return''' <tex>(p_1(x) == 1) \land (p_2(x) == 0)</tex>

* Для языка <tex> L_1 \times L_2 :</tex>

<tex>p(\langle x, y \rangle)</tex>
'''return''' <tex>(p_1(x) == 1) \land (p_2(y) == 1)</tex>

* Для языка <tex>L_1^* :</tex>

<tex>p(x)</tex>
'''for''' <tex>x_i :</tex> разбиение <tex>x</tex>
'''if''' <tex>(p_1(x_i) == 1)</tex>
'''then return''' 1
'''return''' 0

Разрешатель будет перебирать все возможные разбиения данного ему слова на подслова, и для каждого проверять принадлежность <tex> L_1 </tex>. Если хотя бы в одном разбиении все подслова будут принадлежать <tex> L_1 </tex>, то все слово принадлежит <tex> L_1^* </tex>, иначе — не принадлежит.

* Для языка <tex> L_1 L_2 : </tex>

<tex>p(x)</tex>
'''for''' <tex>x_1, x_2 :</tex> разбиение <tex>x</tex>
'''if''' <tex>(p_1(x_1) == 1 \land p_2(x_2) == 1)</tex>
'''then return''' 1
'''return''' 0

Разрешатель будет перебирать все возможные разбиения на два слова и проверять принадлежность первого слова <tex> L_1 </tex> и второго слова <tex> L_2 </tex>. Если хотя бы для одного разбиения оба разрешателя вернут 1, то слово принадлежит <tex> L_1 L_2 </tex>, иначе — не принадлежит.
}}

{{Теорема
|statement=
Языки <tex> L_1, L_2 </tex> –- перечислимы, тогда языки

<tex>\left. \begin{array}{lll} L_1 \cup L_2 \\ L_1 \cap L_2 \\ L_1 \times L_2\\ L_1^* \\ L_1 L_2 \end{array} \right\} </tex> тоже перечислимы.
|proof=

Пусть <tex>p_1</tex> и <tex>p_2</tex> — полуразрешающие программы для языков <tex>L_1</tex> и <tex>L_2</tex> соответственно. Для доказательства достаточно написать полуразрешающую или перечисляющую программу для каждого случая. Заметим, что <tex>p_1</tex> и <tex>p_2</tex> могут зависнуть при использовании в полуразрешающей программе для соответствующего языка, но это допустимо.

* Для языка <tex> L_1 \cup L_2 :</tex>

полуразрешающая программа:

<tex>p(x)</tex>
'''for''' <tex>k = 1\ .. \ \infty </tex>
'''if''' <tex> (p_1|_k(x) == 1) \lor (p_2|_k(x) == 1) </tex>
'''then return 1'''

Перечислитель же для этого языка будет по очереди на один шаг запускать перечислители для <tex>L_1</tex> и <tex>L_2</tex> и выдавать по очереди слова из <tex>L_1</tex> и <tex>L_2</tex> соответственно.

* Для языка <tex> L_1 \cap L_2 :</tex>

полуразрешающая программа:

<tex>p(x)</tex>
'''for''' <tex>k = 1\ .. \ \infty </tex>
'''if''' <tex> (p_1|_k(x) == 1) \land (p_2|_k(x) == 1) </tex>
'''then return 1'''

* Для языка <tex> L_1 \times L_2 :</tex>

полуразрешающая программа:

<tex>p(\langle x, y \rangle)</tex>
'''for''' <tex>k = 1\ .. \ \infty </tex>
'''if''' <tex> (p_1|_k(x) == 1) \land (p_2|_k(y) == 1) </tex>
'''then return 1'''

* Для языка <tex> L_1^* :</tex>

полуразрешающая программа (по аналогии с <tex>L_1^*</tex> для разрешимого <tex>L_1</tex>):

<tex>p(x)</tex>
'''for''' <tex>x_i :</tex> разбиение <tex>x</tex>
'''if''' <tex>(p_1(x_i) == 1)</tex>
'''then return''' 1

Перечислитель строится следующим образом: запускаем перечислитель для <tex> L_1 </tex> в цикле по тайм-лимиту и запоминаем выданные им слова. При выдаче каждого нового слова перебираем все возможные перестановки уже выданных слов и выдаем их.

* Для языка <tex> L_1 L_2 : </tex>

полуразрешающая программа:

<tex>p(x)</tex>
'''for''' <tex>x_1, x_2 :</tex> разбиение <tex>x</tex>
'''if''' <tex>(p_1(x_1) == 1 \land p_2(x_2) == 1)</tex>
'''then return''' 1

Перечислитель для <tex> L_1 L_2 </tex> строим следующим образом: запускаем одновременно перечислители для <tex> L_1 </tex> и <tex> L_2 </tex>, запоминая все выданные слова. При выдаче новых слов перебираем все возможные пары из запомненных слов и выдаем их конкатенацию.
}}

{{Теорема
|statement=
Языки <tex> L_1, L_2 </tex> –- перечислимы, тогда языки

<tex>\left. \begin{array}{lll} \overline{L_1} \\ L_1 \backslash L_2 \end{array} \right\} </tex> могут быть не перечислимы.

|proof=

Рассмотрим язык <tex> \overline{L_1} </tex>. Предположим, что он перечислим. Тогда имея какое-либо слово, мы можем одновременно запустить перечислители для <tex> L_1 </tex> и <tex> \overline{L_1} </tex>. В какой-то момент времени слово появится либо в выводе перечислителя для <tex> L_1 </tex>, либо в выводе перечислителя для <tex> \overline{L_1} </tex>. Тогда получится что <tex> L_1 </tex> разрешим, так как про любое слово мы можем узнать принадлежит оно <tex> L_1 </tex> или не принадлежит. Но мы знаем, что существуют перечислимые, но не разрешимые языки, следовательно, язык <tex> \overline{L_1} </tex> может быть не перечислим.

Теперь рассмотрим <tex> L_1 \backslash L_2 </tex>. В качестве <tex> L_1 </tex> возьмем язык, состоящий из всех слов. Тогда получится, что язык <tex> L_1 \backslash L_2 </tex> это <tex> \overline{L_2} </tex>. Про язык <tex> \overline{L_2} </tex> мы знаем, что он перечислим не всегда, следовательно и язык <tex> L_1 \backslash L_2 </tex> также не всегда перечислим.
}}

Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций

2011-12-18T05:47:07Z

Roman Livarsky:

{{Теорема
|statement=
Языки <tex> L_1, L_2 </tex> –- разрешимы, тогда языки

<tex>\left. \begin{array}{lll} L_1 \cup L_2 \\ L_1 \cap L_2 \\ \overline{L_1} \\ L_1 \backslash L_2 \\ L_1 \times L_2 \\L_1^* \\ L_1 L_2 \end{array} \right\} </tex> тоже разрешимы.
|proof=
Пусть <tex>p_1</tex> и <tex>p_2</tex> — разрешающие программы для языков
<tex>L_1</tex> и <tex>L_2</tex> соответственно. Для доказательства достаточно написать разрешающую программу (разрешатель) для каждого случая.

Разрешающая программа для языка <tex> L_1 \cup L_2 :</tex>

<tex>p(x)</tex>
'''return''' <tex>(p_1(x) == 1) \lor (p_2(x) == 1)</tex>

Для языка <tex> L_1 \cap L_2 :</tex>

<tex>p(x)</tex>
'''return''' <tex>(p_1(x) == 1) \land (p_2(x) == 1)</tex>

Для языка <tex> \overline{L_1} :</tex>

<tex>p(x)</tex>
'''return''' <tex>(p_1(x) == 0)</tex>

Для языка <tex> L_1 \backslash L_2 :</tex>

<tex>p(x)</tex>
'''return''' <tex>(p_1(x) == 1) \land (p_2(x) == 0)</tex>

Для языка <tex> L_1 \times L_2 :</tex>

<tex>p(\langle x, y \rangle)</tex>
'''return''' <tex>(p_1(x) == 1) \land (p_2(y) == 1)</tex>

Для языка <tex>L_1^* :</tex>

<tex>p(x)</tex>
'''for''' <tex>x_i :</tex> разбиение <tex>x</tex>
'''if''' <tex>(p_1(x_i) == 1)</tex>
'''then return''' 1
'''return''' 0

Разрешатель будет перебирать все возможные разбиения данного ему слова на подслова, и для каждого проверять принадлежность <tex> L_1 </tex>. Если хотя бы в одном разбиении все подслова будут принадлежать <tex> L_1 </tex>, то все слово принадлежит <tex> L_1^* </tex>, иначе — не принадлежит.

Для языка <tex> L_1 L_2 : </tex>

<tex>p(x)</tex>
'''for''' <tex>x_1, x_2 :</tex> разбиение <tex>x</tex>
'''if''' <tex>(p_1(x_1) == 1 \land p_2(x_2) == 1)</tex>
'''then return''' 1
'''return''' 0

Разрешатель будет перебирать все возможные разбиения на два слова и проверять принадлежность первого слова <tex> L_1 </tex> и второго слова <tex> L_2 </tex>. Если хотя бы для одного разбиения оба разрешателя вернут 1, то слово принадлежит <tex> L_1 L_2 </tex>, иначе — не принадлежит.
}}

{{Теорема
|statement=
Языки <tex> L_1, L_2 </tex> –- перечислимы, тогда языки

<tex>\left. \begin{array}{lll} L_1 \cup L_2 \\ L_1 \cap L_2 \\ L_1 \times L_2\\ L_1^* \\ L_1 L_2 \end{array} \right\} </tex> тоже перечислимы.
|proof=

Пусть <tex>p_1</tex> и <tex>p_2</tex> — полуразрешающие программы для языков <tex>L_1</tex> и <tex>L_2</tex> соответственно. Для доказательства достаточно написать полуразрешающую или перечисляющую программу для каждого случая. Заметим, что <tex>p_1</tex> и <tex>p_2</tex> могут зависнуть при использовании в полуразрешающей программе для соответствующего языка, но это допустимо.

Для языка <tex> L_1 \cup L_2 :</tex>

полуразрешающая программа:

<tex>p(x)</tex>
'''for''' <tex>k = 1\ .. \ \infty </tex>
'''if''' <tex> (p_1|_k(x) == 1) \lor (p_2|_k(x) == 1) </tex>
'''then return 1'''

Перечислитель же для этого языка будет по очереди на один шаг запускать перечислители для <tex>L_1</tex> и <tex>L_2</tex> и выдавать по очереди слова из <tex>L_1</tex> и <tex>L_2</tex> соответственно.

Для языка <tex> L_1 \cap L_2 :</tex>

полуразрешающая программа:

<tex>p(x)</tex>
'''for''' <tex>k = 1\ .. \ \infty </tex>
'''if''' <tex> (p_1|_k(x) == 1) \land (p_2|_k(x) == 1) </tex>
'''then return 1'''

Для языка <tex> L_1 \times L_2 :</tex>

полуразрешающая программа:

<tex>p(\langle x, y \rangle)</tex>
'''for''' <tex>k = 1\ .. \ \infty </tex>
'''if''' <tex> (p_1|_k(x) == 1) \land (p_2|_k(y) == 1) </tex>
'''then return 1'''

Для языка <tex> L_1^* :</tex>

полуразрешающая программа (по аналогии с <tex>L_1^*</tex> для разрешимого <tex>L_1</tex>):

<tex>p(x)</tex>
'''for''' <tex>x_i :</tex> разбиение <tex>x</tex>
'''if''' <tex>(p_1(x_i) == 1)</tex>
'''then return''' 1

Перечислитель строится следующим образом: запускаем перечислитель для <tex> L_1 </tex> в цикле по тайм-лимиту и запоминаем выданные им слова. При выдаче каждого нового слова перебираем все возможные перестановки уже выданных слов и выдаем их.

Для языка <tex> L_1 L_2 : </tex>

полуразрешающая программа:

<tex>p(x)</tex>
'''for''' <tex>x_1, x_2 :</tex> разбиение <tex>x</tex>
'''if''' <tex>(p_1(x_1) == 1 \land p_2(x_2) == 1)</tex>
'''then return''' 1

Перечислитель для <tex> L_1 L_2 </tex> строим следующим образом: запускаем одновременно перечислители для <tex> L_1 </tex> и <tex> L_2 </tex>, запоминая все выданные слова. При выдаче новых слов перебираем все возможные пары из запомненных слов и выдаем их конкатенацию.
}}

{{Теорема
|statement=
Языки <tex> L_1, L_2 </tex> –- перечислимы, тогда языки

<tex>\left. \begin{array}{lll} \overline{L_1} \\ L_1 \backslash L_2 \end{array} \right\} </tex> могут быть не перечислимы.

|proof=

Рассмотрим язык <tex> \overline{L_1} </tex>. Предположим, что он перечислим. Тогда имея какое-либо слово, мы можем одновременно запустить перечислители для <tex> L_1 </tex> и <tex> \overline{L_1} </tex>. В какой-то момент времени слово появится либо в выводе перечислителя для <tex> L_1 </tex>, либо в выводе перечислителя для <tex> \overline{L_1} </tex>. Тогда получится что <tex> L_1 </tex> разрешим, так как про любое слово мы можем узнать принадлежит оно <tex> L_1 </tex> или не принадлежит. Но мы знаем, что существуют перечислимые, но не разрешимые языки, следовательно, язык <tex> \overline{L_1} </tex> может быть не перечислим.

Теперь рассмотрим <tex> L_1 \backslash L_2 </tex>. В качестве <tex> L_1 </tex> возьмем язык, состоящий из всех слов. Тогда получится, что язык <tex> L_1 \backslash L_2 </tex> это <tex> \overline{L_2} </tex>. Про язык <tex> \overline{L_2} </tex> мы знаем, что он перечислим не всегда, следовательно и язык <tex> L_1 \backslash L_2 </tex> также не всегда перечислим.
}}

Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций

2011-12-18T03:58:53Z

Roman Livarsky:

{{Теорема
|statement=
Языки <tex> L_1, L_2 </tex> –- разрешимы, тогда языки

<tex>\left. \begin{array}{lll} L_1 \cup L_2 \\ L_1 \cap L_2 \\ \overline{L_1} \\ L_1 \backslash L_2 \\ L_1 \times L_2 \\L_1^* \\ L_1 L_2 \end{array} \right\} </tex> тоже разрешимы.
|proof=
Пусть <tex>p_1</tex> и <tex>p_2</tex> — разрешающие программы для языков
<tex>L_1</tex> и <tex>L_2</tex> соответственно. Для доказательства достаточно написать разрешающую программу (разрешитель) для каждого случая.

Разрешающая программа для языка <tex> L_1 \cup L_2 :</tex>

<tex>p(x)</tex>
'''return''' <tex>(p_1(x) == 1) \land (p_2(x) == 1)</tex>

Для языка <tex> L_1 \cap L_2 :</tex>

<tex>p(x)</tex>
'''return''' <tex>(p_1(x) == 1) \lor (p_2(x) == 1)</tex>

Для языка <tex> \overline{L_1} :</tex>

<tex>p(x)</tex>
'''return''' <tex>(p_1(x) == 0)</tex>

Для языка <tex> L_1 \backslash L_2 :</tex>

<tex>p(x)</tex>
'''return''' <tex>(p_1(x) == 1) \land (p_2(x) == 0)</tex>

Для языка <tex> L_1 \times L_2 :</tex>

<tex>p(\langle x, y \rangle)</tex>
'''return''' <tex>(p_1(x) == 1) \land (p_2(y) == 1)</tex>

Для языка <tex>L_1^* :</tex>

<tex>p(x)</tex>
'''for''' <tex>x_i :</tex> разбиение <tex>x</tex>
'''if''' <tex>(p_1(x_i) == 1)</tex>
'''then return''' 1
'''return''' 0

Разрешатель будет перебирать все возможные разбиения данного ему слова на подслова, и для каждого проверять принадлежность <tex> L_1 </tex>. Если хотя бы в одном разбиении все подслова будут принадлежать <tex> L_1 </tex>, то все слово принадлежит <tex> L_1^* </tex>, иначе — не принадлежит.

Для языка <tex> L_1 L_2 : </tex>

<tex>p(x)</tex>
'''for''' <tex>x_1, x_2 :</tex> разбиение <tex>x</tex>
'''if''' <tex>(p_1(x_1) == 1 \land p_2(x_2) == 1)</tex>
'''then return''' 1
'''return''' 0

Разрешитель будет перебирать все возможные разбиения на два слова и проверять принадлежность первого слова <tex> L_1 </tex> и второго слова <tex> L_2 </tex>. Если хотя бы для одного разбиения оба разрешателя вернут 1, то слово принадлежит <tex> L_1 L_2 </tex>, иначе — не принадлежит.
}}

{{Теорема
|statement=
<tex> L_1, L_2 </tex> –- перечислимы, тогда

<tex>\left. \begin{array}{lll} L_1 \cup L_2 \\ L_1 \cap L_2 \\ L_1^* \\ L_1 L_2 \end{array} \right\} </tex> перечислимы
<tex>\left. \begin{array}{lll} \bar{L_1} \\ L_1 \backslash L_2 \end{array} \right\} </tex> могут быть не перечислимы
|proof=
Для <tex> L_1 \cup L_2 </tex> перечислитель будет по очереди на один шаг запускать перечислители <tex> L_1 </tex> и <tex> L_2 </tex> и выдавать по очереди слова из <tex> L_1 </tex> и <tex> L_2 </tex>. Дальше воспользуемся возможностью построить полувычислитель для перечислимого языка. Для языка <tex> L_1 \cap L_2 </tex> построим полувычислитель. Запустим по очереди полувычислители для <tex> L_1 </tex> и <tex> L_2 </tex>. Если слово принадлежит <tex> L_1 \cap L_2 </tex>, то оба полувычислителя выдадут 1, иначе один из полувычислителей зависнет, и полувычислитель для <tex> L_1 \cap L_2 </tex> тоже зависнет, что допустимо. Для <tex> L_1^* </tex> перечислитель строится следующим образом: запускаем перечислитель для <tex> L_1 </tex> в цикле и запоминаем выданные им слова. При выдаче каждого нового слова перебираем все возможные перестановки уже выданных слов и выдаем их. Перечислитель для <tex> L_1 L_2 </tex> строим следующим образом: запускаем одновременно перечислители для <tex> L_1 </tex> и <tex> L_2 </tex>, запоминая все выданные слова. При выдаче новых слов перебираем все возможные пары из запомненных слов и выдаем их.

Рассмотрим язык <tex> \bar{L_1} </tex>. Предположим, что он перечислим. Тогда имея какое-либо слово, мы можем одновременно запустить перечислители для <tex> L_1 </tex> и <tex> \bar{L_1} </tex>. В какой-то момент времени слово появится либо в выводе перечислителя для <tex> L_1 </tex>, либо в выводе перечислителя для <tex> \bar{L_1} </tex>. Тогда получится что <tex> L_1 </tex> разрешим, так как про любое слово мы можем узнать принадлежит оно <tex> L_1 </tex> или не принадлежит. Но мы знаем, что существуют перечислимые, но не разрешимые языки, следовательно, язык <tex> \bar{L_1} </tex> может быть не перечислим. Теперь рассмотрим <tex> L_1 \backslash L_2 </tex>. В качестве <tex> L_1 </tex> возьмем язык, состоящий из всех слов. Тогда получится, что язык <tex> L_1 \backslash L_2 </tex> это <tex> \bar{L_2} </tex>. Про язык <tex> \bar{L_2} </tex> мы знаем, что он перечислим не всегда, следовательно и язык <tex> L_1 \backslash L_2 </tex> также не всегда перечислим.
}}

Сведение задачи RMQ к задаче LCA

2011-05-06T03:48:25Z

Roman Livarsky:

== Постановка задачи RMQ ==
Дан массив <tex>A[1..N]</tex>. Поступают запросы вида <tex>(i, j)</tex>, на каждый запрос требуется найти минимум в массиве <tex>A</tex>, начиная с позиции <tex>i</tex> и заканчивая позицией <tex>j</tex>.
== Алгоритм ==
[[Файл:Wiki.PNG|thumb|right|300x160px|Пример построенного дерева для массива А]]
Декартово дерево (Сartesian tree) на массиве <tex>A[1..N]</tex> - это бинарное дерево, рекурсивно определенное следующим образом:
* Корнем дерева является минимальное значение в массиве <tex>A</tex>, скажем <tex>A[i]</tex>.
* Левым поддеревом является декартово дерево на массиве <tex>A[1..i-1]</tex>.
* Правым поддеревом является декартово дерево на массиве <tex>A[i+1..N]</tex>.
Построим декартово дерево на массиве <tex>A</tex>. Тогда <tex>RMQ(i, j)</tex> = <tex>LCA(A[i], A[j])</tex>.
== Доказательство ==
Мы знаем что:
* 1. Любая вершина дерева всегда имеет меньшее значение, чем её дети. Тогда любой предок <tex>A[i]</tex> или <tex>A[j]</tex> меньше их самих.
* 2. Все вершины, которые лежат в дереве на пути от <tex>A[i]</tex> до <tex>A[j]</tex>, а так же их поддеревья образуют подмассив <tex>A[i..j]</tex> (возьмём только правое поддерево у <tex>A[i]</tex> и левое поддерево у <tex>A[j]</tex>). Т.к. всё, что левее <tex>i</tex>-го элемента в массиве, лежит левее <tex>A[i]</tex> в дереве, и всё, что правее <tex>j</tex>-го, лежит правее <tex>A[j]</tex>. A дерево содержит все элементы <tex>A[1..N]</tex>.
* 3. Из всех вершин, определенных в п.2, <tex>LCA(A[i], A[j])</tex> ближайший к корню и по п.1 имеет наименьшее значение в подмассиве <tex>A[i..j]</tex>.
== Сложность ==
Построение дерева наивным алгоритмом <tex>O(n^2)</tex>. Существует алгоритм построения за <tex>O(n)</tex>.

Препроцессинг для <tex>LCA</tex> - <tex>O(n)</tex> и ответ на запрос <tex>O(1)</tex>.
В итоге получили <tex>RMQ</tex> {построение <tex>O(n)</tex>, запрос <tex>O(1)</tex>}.
== См.также ==
*[[Сведение задачи LCA к задаче RMQ]]

Файл:Wiki.PNG

2011-05-06T03:44:12Z

Roman Livarsky: Пример дерева для массива

Пример дерева для массива

Сведение задачи RMQ к задаче LCA

2011-05-06T03:29:23Z

Roman Livarsky:

== Постановка задачи RMQ ==
Дан массив <tex>A[1..N]</tex>. Поступают запросы вида <tex>(i, j)</tex>, на каждый запрос требуется найти минимум в массиве <tex>A</tex>, начиная с позиции <tex>i</tex> и заканчивая позицией <tex>j</tex>.
== Алгоритм ==
Декартово дерево(Сartesian tree) на массиве <tex>A[1..N]</tex> - это бинарное дерево, рекурсивно определенное следующим образом:
* Корнем дерева является минимальное значение в массиве <tex>A</tex>, скажем <tex>A[i]</tex>.
* Левым поддеревом является декартово дерево на массиве <tex>A[1..i-1]</tex>.
* Правым поддеревом является декартово дерево на массиве <tex>A[i+1..N]</tex>.
Построим декартово дерево на массиве <tex>A</tex>. Тогда <tex>RMQ(i, j)</tex> = <tex>LCA(A[i], A[j])</tex>.
== Доказательство ==
Мы знаем что:
* 1. Любая вершина дерева всегда имеет меньшее значение, чем её дети. Тогда любой предок <tex>A[i]</tex> или <tex>A[j]</tex> меньше их самих.
* 2. Все вершины, которые лежат в дереве на пути от <tex>A[i]</tex> до <tex>A[j]</tex>, а так же их поддеревья образуют подмассив <tex>A[i..j]</tex>(возьмём только правое поддерево у <tex>A[i]</tex> и левое поддерево у <tex>A[j]</tex>). Т.к. всё, что левее <tex>i</tex>-го элемента в массиве, лежит левее <tex>A[i]</tex> в дереве, и всё, что правее <tex>j</tex>-го, лежит правее <tex>A[j]</tex>. A дерево содержит все элементы <tex>A[1..N]</tex>.
* 3. Из всех вершин, определенных в п.2, <tex>LCA(A[i], A[j])</tex> ближайший к корню и по п.1 имеет наименьшее значение в подмассиве <tex>A[i..j]</tex>.
== Сложность ==
Построение дерева наивным алгоритмом <tex>O(n^2)</tex>. Существует алгоритм построение за <tex>O(n)</tex>.
Препроцессинг для <tex>LCA</tex> - <tex>O(n)</tex> и ответ на запрос <tex>O(1)</tex>. В итоге получили <tex>RMQ</tex> {построение <tex>O(n)</tex>, запрос <tex>O(1)</tex>}.
== См.также ==
*[[Сведение задачи LCA к задаче RMQ]]

Сведение задачи RMQ к задаче LCA

2011-05-06T03:28:39Z

Roman Livarsky:

== Постановка задачи RMQ ==
Дан массив <tex>A[1..N]</tex>. Поступают запросы вида <tex>(i, j)</tex>, на каждый запрос требуется найти минимум в массиве <tex>A</tex>, начиная с позиции <tex>i</tex> и заканчивая позицией <tex>j</tex>.
== Алгоритм ==
Декартово дерево(Сartesian tree) на массиве <tex>A[1..N]</tex> - это бинарное дерево, рекурсивно определенное следующим образом:
* 1. Корнем дерева является минимальное значение в массиве <tex>A</tex>, скажем <tex>A[i]</tex>.
* 2. Левым поддеревом является декартово дерево на массиве <tex>A[1..i-1]</tex>.
* 3. Правым поддеревом является декартово дерево на массиве <tex>A[i+1..N]</tex>.
Построим декартово дерево на массиве <tex>A</tex>. Тогда <tex>RMQ(i, j)</tex> = <tex>LCA(A[i], A[j])</tex>.
== Доказательство ==
Мы знаем что:
* 1. Любая вершина дерева всегда имеет меньшее значение, чем её дети. Тогда любой предок <tex>A[i]</tex> или <tex>A[j]</tex> меньше их самих.
* 2. Все вершины, которые лежат в дереве на пути от <tex>A[i]</tex> до <tex>A[j]</tex>, а так же их поддеревья образуют подмассив <tex>A[i..j]</tex>(возьмём только правое поддерево у <tex>A[i]</tex> и левое поддерево у <tex>A[j]</tex>). Т.к. всё, что левее <tex>i</tex>-го элемента в массиве, лежит левее <tex>A[i]</tex> в дереве, и всё, что правее <tex>j</tex>-го, лежит правее <tex>A[j]</tex>. A дерево содержит все элементы <tex>A[1..N]</tex>.
* 3. Из всех вершин, определенных в п.2, <tex>LCA(A[i], A[j])</tex> ближайший к корню и по п.1 имеет наименьшее значение в подмассиве <tex>A[i..j]</tex>.
== Сложность ==
Построение дерева наивным алгоритмом <tex>O(n^2)</tex>. Существует алгоритм построение за <tex>O(n)</tex>.
Препроцессинг для <tex>LCA</tex> - <tex>O(n)</tex> и ответ на запрос <tex>O(1)</tex>. В итоге получили <tex>RMQ</tex> {построение <tex>O(n)</tex>, запрос <tex>O(1)</tex>}.
== См.также ==
*[[Сведение задачи LCA к задаче RMQ]]

Сведение задачи RMQ к задаче LCA

2011-05-06T03:20:02Z

Roman Livarsky: Новая страница: «== Постановка задачи RMQ == Дан массив <tex>A[1..N]</tex>. Поступают запросы вида <tex>(i, j)</tex>, на каждый …»

== Постановка задачи RMQ ==
Дан массив <tex>A[1..N]</tex>. Поступают запросы вида <tex>(i, j)</tex>, на каждый запрос требуется найти минимум в массиве <tex>A</tex>, начиная с позиции <tex>i</tex> и заканчивая позицией <tex>j</tex>.
== Алгоритм ==
Декартово дерево(Сartesian tree) на массиве <tex>A[1..N]</tex> - это бинарное дерево, рекурсивно определенное следующим образом:
* Корнем дерева является минимальное значение в массиве <tex>А</tex>,скажем <tex>A[i]</tex>.
* Левым поддеревом является декартово дерево на массиве <tex>A[1..i-1]</tex>.
* Правым поддеревом является декартово дерево на массиве <tex>A[i+1..N]</tex>.
Построим декартово дерево на массиве <tex>A</tex>. Тогда <tex>RMQ(i, j)</tex> = <tex>LCA(A[i], A[j])</tex>.
== Доказательство ==
Мы знаем что:
* 1. Любая вершина дерева всегда имеет меньшее значение, чем её дети. Тогда любой предок <tex>A[i]</tex> или <tex>A[j]</tex> меньше их самих.
* 2. Все вершины, которые лежат в дереве на пути от <tex>A[i]</tex> до <tex>A[j]</tex>, а так же их поддеревья образуют подмассив <tex>A[i..j]</tex>(возьмём только правое поддерево у <tex>A[i]</tex> и левое поддерево у <tex>A[j]</tex>). Т.к. всё, что левее <tex>i</tex>-го элемента в массиве, лежит левее <tex>A[i]</tex> в дереве, и всё, что правее <tex>j</tex>-го, лежит правее <tex>A[j]</tex>. A дерево содержит все элементы <tex>A[1..N]</tex>.
* 3. Из всех вершин, определенных в п.2, <tex>LCA(A[i], A[j])</tex> ближайший к корню и по п.1 имеет наименьшее значение в подмассиве <tex>A[i..j]</tex>.
== Сложность ==
Построение дерева наивным алгоритмом <tex>O(n^2)</tex>. Существует алгоритм построение за <tex>O(n)</tex>.
Препроцессинг для <tex>LCA O(n)</tex> и ответ на запрос <tex>O(1)</tex>. В итоге получили <tex>RMQ</tex> {построение <tex>O(n)</tex>, запрос <tex>O(1)</tex>}.
== См.также ==
*[[Сведение задачи RMQ к задаче LCA]]

Сведение задачи о назначениях к задаче о потоке минимальной стоимости

2011-01-15T22:02:03Z

Roman Livarsky:

== Постановка задачи ==
* Дана квадратная матрица <tex>A_{N\times N}</tex>. Нужно выбрать в ней <tex>N</tex> элементов так, чтобы в каждой строке и столбце был выбран только один элемент, а сумма значений этих элементов была наименьшей.
* Имеется <tex>N</tex> заказов и <tex>N</tex> станков. Про каждый заказ известна стоимость его изготовления на каждом станке. На каждом станке можно выполнять только один заказ. Требуется распределить все заказы по станкам так, чтобы минимизировать суммарную стоимость.

== Сведение к задаче о потоке минимальной стоимости ==
[[Файл:pic.PNG|thumb|right|275x250px|Пример построенного графа для матрицы А]]
Построим двудольный граф <tex>G</tex> следующим образом:
* Имеется исток <tex>S</tex> и сток <tex>T</tex>.
* В первой доле находятся <tex>N</tex> вершин, соответствующие строкам матрицы или заказам.
* Во второй <tex>N</tex> вершин, соответствующие столбцам матрицы или станкам.
* Между каждой вершиной <tex>i</tex> первой доли и каждой вершиной <tex>j</tex> второй доли проведём ребро с пропускной способностью 1 и стоимостью <tex>A_{ij}</tex>.
* От истока <tex>S</tex> проведём рёбра ко всем вершинам <tex>i</tex> первой доли с пропускной способностью 1 и стоимостью 0.
* От каждой вершины второй доли <tex>j</tex> к стоку <tex>T</tex> проведём ребро с пропускной способностью 1 и стоимостью 0.

Найдём в полученном графе <tex>G</tex> максимальный [[Поток минимальной стоимости|поток минимальной стоимости]]. 
Понятно, что величина потока будет равна <tex>N</tex>. Заметим, что для каждой вершины <tex>i</tex> из первой доли найдётся только одна вершина <tex>j</tex> из второй доли, такая, что поток <tex>f(i, j) = 1</tex>. Поскольку найденный поток имеет минимальную стоимость, то сумма стоимостей выбранных рёбер будет наименьшей из возможных. Поэтому, это взаимно однозначное соответствие между вершинами первой доли и вершинами второй доли является решением задачи.

== Асимптотика ==
Асимптотика этого решения равна асимптотике алгоритма, выбранного для поиска потока.
== Источники ==
[http://e-maxx.ru/algo/assignment_mincostflow Задача о назначениях. Решение с помощью min-cost-flow]

Файл:Pic.PNG

2011-01-15T21:58:17Z

Roman Livarsky: загружена новая версия «Файл:Pic.PNG»: Пример построенного графа для данной матрицы А

Пример построенного графа для данной матрицы А

Сведение задачи о назначениях к задаче о потоке минимальной стоимости

2011-01-15T21:40:20Z

Roman Livarsky:

== Постановка задачи ==
* Дана квадратная матрица <tex>A_{N\times N}</tex>. Нужно выбрать в ней <tex>N</tex> элементов так, чтобы в каждой строке и столбце был выбран только один элемент, а сумма значений этих элементов была наименьшей.
* Имеется <tex>N</tex> заказов и <tex>N</tex> станков. Про каждый заказ известна стоимость его изготовления на каждом станке. На каждом станке можно выполнять только один заказ. Требуется распределить все заказы по станкам так, чтобы минимизировать суммарную стоимость.

== Сведение к задаче о потоке минимальной стоимости ==
[[Файл:pic.PNG|thumb|right|275x250px|Пример построенного графа для матрицы А]]
Построим двудольный граф <tex>G</tex> следующим образом:
* Имеется исток <tex>S</tex> и сток <tex>T</tex>.
* В первой доле находятся <tex>N</tex> вершин, соответствующие строкам матрицы или заказам.
* Во второй <tex>N</tex> вершин, соответствующие столбцам матрицы или станкам.
* Между каждой вершиной <tex>i</tex> первой доли и каждой вершиной <tex>j</tex> второй доли проведём ребро с пропускной способностью 1 и стоимостью <tex>A_{ij}</tex>.
* От истока <tex>S</tex> проведём рёбра ко всем вершинам <tex>i</tex> первой доли с пропускной способностью 1 и стоимостью 0.
* От каждой вершины второй доли <tex>j</tex> к стоку <tex>T</tex> проведём ребро с пропускной способностью 1 и стоимостью 0.

Найдём в полученном графе <tex>G</tex> максимальный [[Поток минимальной стоимости|поток минимальной стоимости]]. 
Понятно, что величина потока будет равна <tex>N</tex>. Заметим, что для каждой вершины <tex>i</tex> из первой доли найдётся только одна вершина <tex>j</tex> из второй доли, такая, что поток <tex>f(i, j) = 1</tex>. Поскольку найденный поток имеет минимальную стоимость, то сумма стоимостей выбранных рёбер будет наименьшей из возможных. Поэтому, это взаимно однозначное соответствие между вершинами первой доли и вершинами второй доли является решением задачи.

== Асимптотика ==
Очевидно, асимптотика этого решения составляет <tex>O(N^5)</tex>.
== Источники ==
[http://e-maxx.ru/algo/assignment_mincostflow Задача о назначениях. Решение с помощью min-cost-flow]

Файл:Pic.PNG

2011-01-15T21:37:18Z

Roman Livarsky: Пример построенного графа для данной матрицы А

Пример построенного графа для данной матрицы А

Сведение задачи о назначениях к задаче о потоке минимальной стоимости

2011-01-14T08:41:29Z

Roman Livarsky:

== Постановка задачи ==
* Дана квадратная матрица <tex>A_{N\times N}</tex>. Нужно выбрать в ней <tex>N</tex> элементов так, чтобы в каждой строке и столбце был выбран только один элемент, а сумма значений этих элементов была наименьшей.
* Имеется <tex>N</tex> заказов и <tex>N</tex> станков. Про каждый заказ известна стоимость его изготовления на каждом станке. На каждом станке можно выполнять только один заказ. Требуется распределить все заказы по станкам так, чтобы минимизировать суммарную стоимость.

== Сведение к задаче о потоке минимальной стоимости ==
Построим двудольный граф <tex>G</tex> следующим образом:
* Имеется сток <tex>S</tex> и исток <tex>T</tex>.
* В первой доле находятся <tex>N</tex> вершин, соответствующие строкам матрицы или заказам.
* Во второй <tex>N</tex> вершин, соответствующие столбцам матрицы или станкам.
* Между каждой вершиной <tex>i</tex> первой доли и каждой вершиной <tex>j</tex> второй доли проведём ребро с пропускной способностью 1 и стоимостью <tex>A_{ij}</tex>.
* От истока <tex>S</tex> проведём рёбра ко всем вершинам <tex>i</tex> первой доли с пропускной способностью 1 и стоимостью 0.
* От каждой вершины второй доли <tex>j</tex> к стоку <tex>T</tex> проведём ребро с пропускной способностью 1 и стоимостью 0.

Найдём в полученном графе <tex>G</tex> максимальный [[Поток минимальной стоимости|поток минимальной стоимости]]. 
Понятно, что величина потока будет равна <tex>N</tex>. Заметим, что для каждой вершины <tex>i</tex> из первой доли найдётся только одна вершина <tex>j</tex> из второй доли, такая, что поток <tex>F_{ij} = 1</tex>. Поскольку найденный поток имеет минимальную стоимость, то сумма стоимостей выбранных рёбер будет наименьшей из возможных. Поэтому, это взаимно однозначное соответствие между вершинами первой доли и вершинами второй доли является решением задачи.

== Источники ==
[http://e-maxx.ru/algo/assignment_mincostflow Задача о назначениях. Решение с помощью min-cost-flow]

Сведение задачи о назначениях к задаче о потоке минимальной стоимости

2011-01-14T08:36:37Z

Roman Livarsky: Новая страница: «== Постановка задачи == * Дана квадратная матрица <tex>A_{N\times N}</tex>. Нужно выбрать в ней <tex>N</tex> э…»

== Постановка задачи ==
* Дана квадратная матрица <tex>A_{N\times N}</tex>. Нужно выбрать в ней <tex>N</tex> элементов так, чтобы в каждой строке и столбце был выбран только один элемент, а сумма значений этих элементов была наименьшей.
* Имеется <tex>N</tex> заказов и <tex>N</tex> станков. Про каждый заказ известна стоимость его изготовления на каждом станке. На каждом станке можно выполнять только один заказ. Требуется распределить все заказы по станкам так, чтобы минимизировать суммарную стоимость.

== Сведение к задаче о потоке минимальной стоимости ==
Построим двудольный граф <tex>G</tex> следующим образом:
* Имеется сток <tex>S</tex> и исток <tex>T</tex>.
* В первой доле находятся <tex>N</tex> вершин, соответствующие строкам матрицы или заказам.
* Во второй <tex>N</tex> вершин, соответствующие столбцам матрицы или станкам.
* Между каждой вершиной <tex>i</tex> первой доли и каждой вершиной <tex>j</tex> второй доли проведём ребро с пропускной способностью 1 и стоимостью <tex>A_{ij}</tex>.
* От истока <tex>S</tex> проведём рёбра ко всем вершинам <tex>i</tex> первой доли с пропускной способностью 1 и стоимостью 0.
* От каждой вершины второй доли <tex>j</tex> к стоку <tex>T</tex> проведём ребро с пропускной способностью 1 и стоимостью 0.

Найдём в полученном графе <tex>G</tex> максимальный [[Поток минимальной стоимости|поток минимальной стоимости]]. 
Понятно, что величина потока будет равна <tex>N</tex>. Заметим, что для каждой вершины <tex>i</tex> из первой доли найдётся только одна вершина <tex>j</tex> из второй доли, такая, что поток <tex>F_{ij} = 1</tex>. Поскольку найденный поток имеет минимальную стоимость, то сумма стоимостей выбранных рёбер будет наименьшей из возможных. Поэтому, это взаимно однозначное соответствие между вершинами первой доли и вершинами второй доли является решением задачи.

Теорема Дирака

2010-10-28T03:02:49Z

Roman Livarsky:

{{Теорема
|statement=
Если <tex>n > 3</tex> и <tex>deg\ v \ge n/2</tex> для любой вершины <tex>v</tex> неориентированного графа <tex>G</tex>, то <tex>G</tex> - гамильтонов граф.
|proof=
По [[Теорема Хватала|теореме Хватала]]: для <tex>\forall k</tex> верна импликация <tex>d_k \le k < n/2 \Rightarrow d_{n-k} \ge n-k</tex>
}}

== Источники ==
Харари Ф. - Теория графов. '''ISBN 978-5-397-00622-4'''

Теорема Оре

2010-10-28T02:59:29Z

Roman Livarsky:

{{Теорема
|statement=
Если <tex>n \ge 3</tex> и <tex>deg\ u + deg\ v \ge n</tex> для любых двух различных несмежных вершин <tex>u</tex> и <tex>v</tex> неориентированного графа <tex>G</tex>, то <tex>G</tex> - гамильтонов граф.

|proof=

Пусть, от противного, существует граф <tex>G</tex>, который удовлетворяет условию теоремы, но не является гамильтоновым графом.
Будем добавлять к нему новые ребра до тех пор, пока не получим максимальный негамильтонов граф <tex>G'</tex>. В силу того, что мы только добавляли ребра, условие теоремы не нарушилось.

Пусть <tex>u,v</tex> несмежные вершины в полученном графе <tex>G'</tex>. Если добавить ребро <tex>uv</tex>, появится гамильтонов цикл. Тогда путь <tex>(u,v)</tex> - гамильтонов.

Для вершин <tex>u,v</tex> выполнено <tex>deg\ u + deg\ v \ge n.</tex>

По принципу Дирихле всегда найдутся две смежные вершины <tex> t_1,t_2</tex> на пути <tex>(u,v)</tex> ,т.е. <tex>u..t_1t_2..v</tex> , такие, что существует ребро <tex>ut_2</tex> и ребро <tex>t_1v.</tex>

Действительно, пусть <tex>S=</tex> { <tex> i| e_i=ut_{i+1} \in EG</tex> } и <tex>T = </tex> { <tex> i| f_i=t_iv \in EG</tex> }

Имеем: <tex>\left\vert S \right\vert + \left\vert T \right\vert = deg\ u + deg\ v \ge n </tex>, но <tex>\left\vert S + T \right\vert < n.</tex>

Тогда <tex>\left\vert S\cap T \right\vert = \left\vert S \right\vert + \left\vert T \right\vert - \left\vert S+T \right\vert > 0</tex> т.е. <tex>\exists i| ut_{i+1}\in EG</tex> и <tex> t_iv \in EG.</tex>
Получили противоречие, т.к. <tex>u..t_1v..t_2u</tex> - гамильтонов цикл.
}}

== Источники ==
1. Асанов М. О., Баранский В. А., Расин В. В. - Дискретная математика: Графы, матроиды, алгоритмы. '''ISBN 978-5-8114-1068-2''' 
2. Харари Ф. - Теория графов. '''ISBN 978-5-397-00622-4'''

Теорема Дирака

2010-10-14T02:13:33Z

Roman Livarsky:

Теорема Оре

2010-10-14T02:11:54Z

Roman Livarsky:

Теорема Дирака

2010-10-14T02:02:29Z

Roman Livarsky:

{{Теорема
|statement=
Если <tex>\ n > 3</tex> и <tex>deg\ v \ge n/2</tex> для любой вершины <tex>\ v</tex> неориентированного графа <tex>\ G</tex>, то <tex>\ G</tex> - гамильтонов граф.
|proof=
По [[Теорема Хватала|теореме Хватала]]: для <tex>\forall k</tex> верна импликация <tex>d_k \le k < n/2 \Rightarrow d_{n-k} \ge n-k</tex>
}}

Теорема Дирака

2010-10-11T21:09:04Z

Roman Livarsky:

{{Теорема
|statement=
Если <math>\ n > 3</math> и <math>deg\ v \ge n/2</math> для любой вершины <math>\ v</math> неориентированного графа '''G''', то '''G''' - гамильтонов граф.

|proof=
По теореме Хватала: '''для''' <math>\forall k</math> '''верна импликация''' <math>d_k \le k < n/2 \Rightarrow d_{n-k} \ge n-k</math>
}}

Теорема Оре

2010-10-11T21:00:25Z

Roman Livarsky:

{{Теорема
|statement=
Если <math>n \ge 3</math> и <math>deg\ u + deg \ v \ge n</math> для любых двух различных несмежных вершин <math>\ u</math> и <math>\ v</math> неориентированного графа '''G''', то '''G''' - гамильтонов граф.

|proof=

Пусть, от противного, существует граф '''G''', который удовлетворяет условию теоремы, но не является гамильтоновым графом.
Будем добавлять к нему новые ребра до тех пор, пока не получим максимальный негамильтонов граф '''G''''. В силу того, что мы только добавляли ребра, условие теоремы не нарушилось.

Пусть <math>\ u,v</math> несмежные вершины в полученном графе '''G''''. Если добавить ребро <math>\ uv</math>, появится гамильтонов цикл. Тогда путь <math>\ (u,v)</math> - гамильтонов.

Для вершин <math>\ u,v</math> выполнено <math>deg\ u + deg \ v \ge n.</math>

По принципу Дирихле всегда найдутся две смежные вершины <math>\ t_1,t_2</math> на пути <math>\ (u,v)</math> ,т.е. <math>\ u..t_1t_2..v</math> , такие, что существует ребро <math>\ ut_2</math> и ребро <math>\ t_1v.</math>

Действительно, пусть <math>\ S = </math> { <math> i| e_i=ut_{i+1} \in EG</math> } и <math>\ T = </math> { <math> i| f_i=t_iv \in EG</math> }

Имеем: <math>\left\vert S \right\vert + \left\vert T \right\vert = deg\ u + deg \ v \ge n </math>, но <math>\left\vert S + T \right\vert < n.</math>

Тогда <math>\left\vert S\cap T \right\vert = \left\vert S \right\vert + \left\vert T \right\vert - \left\vert S+T \right\vert > 0</math> т.е. <math>\exists i| ut_{i+1}\in EG</math> и <math> t_iv \in EG.</math>
Получили противоречие, т.к. <math>\ u..t_1v..t_2u</math> - гамильтонов цикл.
}}

Теорема Оре

2010-10-10T23:32:11Z

Roman Livarsky:

{{Теорема
|statement=
Если <math>n \ge 3</math> и <math>deg\ u + deg \ v \ge n</math> для любых двух различных несмежных вершин <math>\ u</math> и <math>\ v</math> неориентированного графа '''G''', то '''G''' - гамильтонов граф.

|proof=

Пусть, от противного, существует граф '''G''', который удовлетворяет условию теоремы, но не является гамильтоновым графом.
Будем добавлять к нему новые ребра до тех пор, пока не получим максимальный негамильтонов граф '''G''''. В силу того, что мы только добавляли ребра, условие теоремы не нарушилось.

Пусть <math>\ u,v</math> несмежные вершины в полученном графе '''G''''. Если добавить ребро <math>\ uv</math>, появится гамильтонов цикл. Тогда путь <math>\ (u,v)</math> - гамильтонов.

Для вершин <math>\ u,v</math> выполнено <math>deg\ u + deg \ v \ge n.</math>

По принципу Дирихле, всегда найдутся две смежные вершины <math>\ t_1,t_2</math> на пути <math>\ (u,v)</math> ,т.е. <math>\ u..t_1t_2..v</math> , такие, что существует ребро <math>\ ut_2</math> и ребро <math>\ t_1v.</math>

Действительно, пусть <math>\ S = </math> { <math> i| e_i=ut_{i+1} \in EG</math> } и <math>\ T = </math> { <math> i| f_i=t_iv \in EG</math> }

Имеем: <math>\left\vert S \right\vert + \left\vert T \right\vert = deg\ u + deg \ v \ge n </math>, но <math>\left\vert S + T \right\vert < n.</math>

Тогда <math>\left\vert S\cap T \right\vert = \left\vert S \right\vert + \left\vert T \right\vert - \left\vert S+T \right\vert > 0</math> т.е. <math>\exists i| ut_{i+1}\in EG</math> и <math> t_iv \in EG.</math>
Получили противоречие, т.к. <math>\ u..t_1v..t_2u</math> - гамильтонов цикл.
}}

Теорема Оре

2010-10-10T23:08:25Z

Roman Livarsky:

{{Теорема
|statement=
Если <math>n \ge 3</math> и <math>deg\ u + deg \ v \ge n</math> для любых двух различных несмежных вершин <math>\ u</math> и <math>\ v</math> неориентированного графа '''G''', то '''G''' - гамильтонов граф.

|proof=

Пусть, от противного, существует граф '''G''', который удовлетворяет условию теоремы, но не является гамильтоновым графом.
Будем добавлять к нему новые ребра до тех пор, пока не получим максимальный негамильтонов граф '''G''''. В силу того, что мы только добавляли ребра, условие теоремы не нарушилось.

Пусть <math>\ u,v</math> несмежные вершины в полученном графе '''G''''. Если добавить ребро <math>\ uv</math>, появится гамильтонов цикл. Тогда путь <math>\ (u,v)</math> - гамильтонов.

Для вершин <math>\ u,v</math> выполнено <math>deg\ u + deg \ v \ge n.</math>

По принципу Дирихле, всегда найдутся две смежные вершины <math>\ t_1,t_2</math> на пути <math>\ (u,v)</math> ,т.е. <math>\ u..t_1t_2..v</math> , такие, что существует ребро <math>\ ut_2</math> и ребро <math>\ t_1v.</math>

Действительно, пусть <math>\ S = </math> { <math> i| e_i=ut_{i+1} \in EG</math> } и <math>\ T = </math> { <math> i| f_i=t_iv \in EG</math> }

Имеем: <math>\left\vert S \right\vert + \left\vert T \right\vert = deg\ u + deg \ v \ge n </math>, но <math>\left\vert S + T \right\vert < n.</math>

И тогда: <math>\left\vert S\cap T \right\vert = \left\vert S \right\vert + \left\vert T \right\vert - \left\vert S+T \right\vert > 0</math> т.е. <math>\exists i| ut_{i+1}\in EG</math> и <math> t_iv \in EG.</math>
Получили противоречие, т.к. <math>\ u..t_1v..t_2u</math> - гамильтонов цикл.
}}

Теорема Оре

2010-10-10T19:54:09Z

Roman Livarsky:

{{Теорема
|statement=
Если <math>n \ge 3</math> и <math>deg\ u + deg \ v \ge n</math> для любых двух различных несмежных вершин <math>\ u</math> и <math>\ v</math> неориентированного графа '''G''', то '''G''' - гамильтонов граф.

|proof=

Пусть, от противного, существует граф '''G''', который удовлетворяет условию теоремы, но не является гамильтоновым графом.
Будем добавлять к нему новые ребра до тех пор, пока не получим максимальный негамильтонов граф '''G''''. В силу того, что мы только добавляли ребра, условие теоремы не нарушилось.

Пусть <math>\ u,v</math> несмежные вершины в полученном графе '''G''''. Если добавить ребро <math>\ uv</math>, появится гамильтонов цикл. Тогда путь <math>\ (u,v)</math> - гамильтонов.

Для вершин <math>\ u,v</math> выполнено <math>deg\ u + deg \ v \ge n</math>.

По принципу Дирихле, всегда найдутся две смежные вершины <math>\ t_1,t_2</math> на пути <math>\ (u,v)</math> ,т.е. <math>\ u..t_1t_2..v</math> , такие, что существует ребро <math>\ ut_2</math> и ребро <math>\ t_1v</math>.
Получили противоречие, т.к. <math>\ u..t_1v..t_2u</math> - гамильтонов цикл.
}}