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

Разрешимые (рекурсивные) языки

2015-11-30T21:42:44Z

212.232.73.136: /* Примеры неразрешимых множества */

== Основные определения ==
{{Определение
|definition= '''Рекурсивный язык''' (англ. ''recursive language'') <tex>L</tex> {{---}} язык, для которого существует программа

<tex>p(w) = \begin{cases}
1, \ w \in L \\
0, \ w \notin L
\end{cases}
</tex>
}}

{{Определение
|definition = Язык <tex>L</tex> называется '''разрешимым''', если существует такая [[Вычислимые функции | вычислимая]] функция <tex>f : \Sigma^* \to \{0, 1\} : x \in L \Leftrightarrow f(x) = 1</tex>.
}}
Если мы рассматриваем язык <tex>L</tex> как проблему, то проблема называется ''разрешимой'', если язык <tex>L</tex> ''рекурсивный''. В противном случае проблема называется ''неразрешимой''. Но часто данные понятия просто отождествляются.

{{Определение
|definition= '''Класс всех разрешимых (рекурсивных) языков''' (англ. ''Class of decidable (recursive) languages'') часто обозначается буквой <tex> \mathrm{R} </tex>.
}}

{{Определение
|id=uni
|definition='''Универсальный язык''' (англ. ''universal language'') <tex> \ U = \{\langle p, x \rangle \ |\ p(x) = 1\} </tex>.
}}

Другими словами, ''универсальный язык'' {{---}} это язык всех таких пар "программа и её вход", что программа на входе возвращает <tex>1</tex>.

Рассмотрим данное определение более детально, для чего докажем вспомогательную лемму:

{{Лемма
|statement=
Существует [[Отображения#Свойства отображений | биекция]] между строками и натуральными числами.
|proof=
Приведем пример такой биекции: занумеруем подряд все строки длины <tex>1</tex>, затем все строки длины <tex>2</tex> и так далее {{---}} нумерация названий столбцов в <tex>Excel</tex>, таким образом, каждому натуральному числу соответствует некоторая строка и наоборот.
}}

Биекция между строками и натуральными числами нам нужна, чтобы передавать пары "текст программы, текст входных данных" в качестве аргументов функций. Передавать можно в следующем виде:

<tex>2^{\mathtt{code}} \cdot 3^{\mathtt{input}}</tex>, где <tex>\mathtt{code}, \ \mathtt{input}</tex> {{---}} есть натуральные числа, соответствующие тексту программы и тексту входных данных соответственно.

Далее считаем, что входные данные программы и сама программа расположены над одним алфавитом <tex>\Sigma</tex>.

== Примеры разрешимых множеств ==
{{Утверждение
|id=st1
|statement=
Язык чётных чисел разрешим.
|proof=
Приведём программу, разрешающую язык чётных чисел:
<tex>p(i) {:} </tex>
'''if''' <tex>i \ \bmod \ 2 == 0 </tex>
'''return''' 1
'''else'''
'''return''' 0

Заметим, что программа нигде не может зависнуть.
}}

{{Утверждение
|statement=
Множество всех рациональных чисел, меньших числа <tex>e</tex> (основания натуральных логарифмов) или <tex>\pi</tex>, разрешимо.
|proof=
Для чисел <tex>e, \ \pi</tex> существуют различные техники нахождения их точного представления, одна их которых описана в статье<ref>[http://www.mathpropress.com/stan/bibliography/spigot.pdf «A Spigot Algorithm for the Digits of Pi»]</ref>, таким образом, возможно получить необходимый знак чисел <tex>e, \ \pi</tex> за конечное время.

Десятичное представление рационального числа <tex>r</tex> может быть получено с любой точностью.

Приведем программу, разрешающую данную проблему для числа <tex>e</tex>:

<tex>p(r) {:} </tex>
'''if''' (<tex>r</tex> < 2)
'''return''' 1
'''if''' (<tex>r</tex> > 3)
'''return''' 0
'''for''' (i = 1 .. <tex>\infty </tex>)
'''if''' (getDigit(<tex>e</tex>, i) > getDigit(<tex>r</tex>, i)) <font color="green">// getDigit {{---}} функция, которая получает i-ую цифру вещественной части переданного числа</font>
'''return''' 1
'''if''' (getDigit(<tex>e</tex>, i) < getDigit(<tex>r</tex>, i))
'''return''' 0
Так как число <tex>e</tex> иррационально, то ответ будет найден за конечное время.
}}

{{Утверждение
|statement=
Множество тех <tex>n</tex>, для которых в числе <tex>\pi</tex> есть не менее <tex>n</tex> девяток подряд, разрешимо.
|proof=
Предположим, что в числе <tex>\pi</tex> встречается <tex>k</tex> девяток подряд, тогда, логично, что встречается и любое число девяток меньших <tex>k</tex>.
Рассмотрим все программы семейства:
<tex>p_0(i) {:} </tex>
'''return''' 1

<tex>p_1(i) {:} </tex>
'''if''' <tex>i < 1 </tex>
'''return''' 1
'''else'''
'''return''' 0

<tex>p_2(i) {:} </tex>
'''if''' <tex>i < 2 </tex>
'''return''' 1
'''else'''
'''return''' 0

<tex>\dots</tex>

<tex>p_k(i) {:} </tex>
'''if''' <tex>i < k </tex>
'''return''' 1
'''else'''
'''return''' 0

<tex>\dots</tex>

По доказанному выше, какая-то программа из этого семейства будет разрешителем для искомого множества. Значит, искомое множество разрешимо.
}}

== Примеры неразрешимых множеств ==

{{Утверждение
|id=st1
|statement=
Универсальный язык неразрешим.
|proof=
Приведём доказательство от противного.

Пусть язык <tex>U</tex> разрешим, тогда существует программа

<tex>u(\langle p, x \rangle) = \begin{cases}
1, \ \langle p, x \rangle \in U \\
0, \ \langle p, x \rangle \notin U
\end{cases}
</tex>

Составим следующую программу:

<tex>r(x) {:} </tex>
'''if''' <tex>u(\langle x, x \rangle) == 1 </tex>
'''while''' ''true''
'''else'''
'''return''' 1

Рассмотрим вызов <tex> r(r) </tex>:
* Eсли <tex> u(\langle r, r \rangle) = 1 </tex>, то условие <tex>\mathrm{if}</tex> выполнится и программа зависнет, но, так как программа <tex> u </tex> разрешает универсальный язык, <tex> u(\langle r, r \rangle) = 1 \Rightarrow r(r) = 1</tex>;
* Eсли <tex> u(\langle r, r \rangle) = 0 </tex>, то условие <tex>\mathrm{if}</tex> не выполнится и программа вернет <tex>1</tex>, но, так как программа <tex> u </tex> разрешает универсальный язык, <tex> u(\langle r, r \rangle) = 0 \Rightarrow r(r) \ne 1</tex>.

Из предположения о разрешимости универсального языка мы пришли к противоречию.
}}

== Примечания ==

<references />

== Источники информации ==
* Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. — М.: МЦНМО, 1999. С. 134. ISBN 5-900916-36-7
* [http://en.wikipedia.org/wiki/Recursive_language Wikipedia — Recursive language]
* [http://ru.wikipedia.org/wiki/%D0%A0%D0%B5%D0%BA%D1%83%D1%80%D1%81%D0%B8%D0%B2%D0%BD%D1%8B%D0%B9_%D1%8F%D0%B7%D1%8B%D0%BA Википедия — Рекурсивный язык]

[[Категория: Теория формальных языков]]
[[Категория: Теория вычислимости]]

Разрешимые (рекурсивные) языки

2015-11-30T21:38:56Z

212.232.73.136: /* Примеры разрешимых множества */

== Основные определения ==
{{Определение
|definition= '''Рекурсивный язык''' (англ. ''recursive language'') <tex>L</tex> {{---}} язык, для которого существует программа

<tex>p(w) = \begin{cases}
1, \ w \in L \\
0, \ w \notin L
\end{cases}
</tex>
}}

{{Определение
|definition = Язык <tex>L</tex> называется '''разрешимым''', если существует такая [[Вычислимые функции | вычислимая]] функция <tex>f : \Sigma^* \to \{0, 1\} : x \in L \Leftrightarrow f(x) = 1</tex>.
}}
Если мы рассматриваем язык <tex>L</tex> как проблему, то проблема называется ''разрешимой'', если язык <tex>L</tex> ''рекурсивный''. В противном случае проблема называется ''неразрешимой''. Но часто данные понятия просто отождествляются.

{{Определение
|definition= '''Класс всех разрешимых (рекурсивных) языков''' (англ. ''Class of decidable (recursive) languages'') часто обозначается буквой <tex> \mathrm{R} </tex>.
}}

{{Определение
|id=uni
|definition='''Универсальный язык''' (англ. ''universal language'') <tex> \ U = \{\langle p, x \rangle \ |\ p(x) = 1\} </tex>.
}}

Другими словами, ''универсальный язык'' {{---}} это язык всех таких пар "программа и её вход", что программа на входе возвращает <tex>1</tex>.

Рассмотрим данное определение более детально, для чего докажем вспомогательную лемму:

{{Лемма
|statement=
Существует [[Отображения#Свойства отображений | биекция]] между строками и натуральными числами.
|proof=
Приведем пример такой биекции: занумеруем подряд все строки длины <tex>1</tex>, затем все строки длины <tex>2</tex> и так далее {{---}} нумерация названий столбцов в <tex>Excel</tex>, таким образом, каждому натуральному числу соответствует некоторая строка и наоборот.
}}

Биекция между строками и натуральными числами нам нужна, чтобы передавать пары "текст программы, текст входных данных" в качестве аргументов функций. Передавать можно в следующем виде:

<tex>2^{\mathtt{code}} \cdot 3^{\mathtt{input}}</tex>, где <tex>\mathtt{code}, \ \mathtt{input}</tex> {{---}} есть натуральные числа, соответствующие тексту программы и тексту входных данных соответственно.

Далее считаем, что входные данные программы и сама программа расположены над одним алфавитом <tex>\Sigma</tex>.

== Примеры разрешимых множеств ==
{{Утверждение
|id=st1
|statement=
Язык чётных чисел разрешим.
|proof=
Приведём программу, разрешающую язык чётных чисел:
<tex>p(i) {:} </tex>
'''if''' <tex>i \ \bmod \ 2 == 0 </tex>
'''return''' 1
'''else'''
'''return''' 0

Заметим, что программа нигде не может зависнуть.
}}

{{Утверждение
|statement=
Множество всех рациональных чисел, меньших числа <tex>e</tex> (основания натуральных логарифмов) или <tex>\pi</tex>, разрешимо.
|proof=
Для чисел <tex>e, \ \pi</tex> существуют различные техники нахождения их точного представления, одна их которых описана в статье<ref>[http://www.mathpropress.com/stan/bibliography/spigot.pdf «A Spigot Algorithm for the Digits of Pi»]</ref>, таким образом, возможно получить необходимый знак чисел <tex>e, \ \pi</tex> за конечное время.

Десятичное представление рационального числа <tex>r</tex> может быть получено с любой точностью.

Приведем программу, разрешающую данную проблему для числа <tex>e</tex>:

<tex>p(r) {:} </tex>
'''if''' (<tex>r</tex> < 2)
'''return''' 1
'''if''' (<tex>r</tex> > 3)
'''return''' 0
'''for''' (i = 1 .. <tex>\infty </tex>)
'''if''' (getDigit(<tex>e</tex>, i) > getDigit(<tex>r</tex>, i)) <font color="green">// getDigit {{---}} функция, которая получает i-ую цифру вещественной части переданного числа</font>
'''return''' 1
'''if''' (getDigit(<tex>e</tex>, i) < getDigit(<tex>r</tex>, i))
'''return''' 0
Так как число <tex>e</tex> иррационально, то ответ будет найден за конечное время.
}}

{{Утверждение
|statement=
Множество тех <tex>n</tex>, для которых в числе <tex>\pi</tex> есть не менее <tex>n</tex> девяток подряд, разрешимо.
|proof=
Предположим, что в числе <tex>\pi</tex> встречается <tex>k</tex> девяток подряд, тогда, логично, что встречается и любое число девяток меньших <tex>k</tex>.
Рассмотрим все программы семейства:
<tex>p_0(i) {:} </tex>
'''return''' 1

<tex>p_1(i) {:} </tex>
'''if''' <tex>i < 1 </tex>
'''return''' 1
'''else'''
'''return''' 0

<tex>p_2(i) {:} </tex>
'''if''' <tex>i < 2 </tex>
'''return''' 1
'''else'''
'''return''' 0

<tex>\dots</tex>

<tex>p_k(i) {:} </tex>
'''if''' <tex>i < k </tex>
'''return''' 1
'''else'''
'''return''' 0

<tex>\dots</tex>

По доказанному выше, какая-то программа из этого семейства будет разрешителем для искомого множества. Значит, искомое множество разрешимо.
}}

== Примеры неразрешимых множества ==

{{Утверждение
|id=st1
|statement=
Универсальный язык неразрешим.
|proof=
Приведём доказательство от противного.

Пусть язык <tex>U</tex> разрешим, тогда существует программа

<tex>u(\langle p, x \rangle) = \begin{cases}
1, \ \langle p, x \rangle \in U \\
0, \ \langle p, x \rangle \notin U
\end{cases}
</tex>

Составим следующую программу:

<tex>r(x) {:} </tex>
'''if''' <tex>u(\langle x, x \rangle) == 1 </tex>
'''while''' ''true''
'''else'''
'''return''' 1

Рассмотрим вызов <tex> r(r) </tex>:
* Eсли <tex> u(\langle r, r \rangle) = 1 </tex>, то условие <tex>\mathrm{if}</tex> выполнится и программа зависнет, но, так как программа <tex> u </tex> разрешает универсальный язык, <tex> u(\langle r, r \rangle) = 1 \Rightarrow r(r) = 1</tex>;
* Eсли <tex> u(\langle r, r \rangle) = 0 </tex>, то условие <tex>\mathrm{if}</tex> не выполнится и программа вернет <tex>1</tex>, но, так как программа <tex> u </tex> разрешает универсальный язык, <tex> u(\langle r, r \rangle) = 0 \Rightarrow r(r) \ne 1</tex>.

Из предположения о разрешимости универсального языка мы пришли к противоречию.
}}

== Примечания ==

<references />

== Источники информации ==
* Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. — М.: МЦНМО, 1999. С. 134. ISBN 5-900916-36-7
* [http://en.wikipedia.org/wiki/Recursive_language Wikipedia — Recursive language]
* [http://ru.wikipedia.org/wiki/%D0%A0%D0%B5%D0%BA%D1%83%D1%80%D1%81%D0%B8%D0%B2%D0%BD%D1%8B%D0%B9_%D1%8F%D0%B7%D1%8B%D0%BA Википедия — Рекурсивный язык]

[[Категория: Теория формальных языков]]
[[Категория: Теория вычислимости]]