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

2015-01-09T18:53:45Z

188.162.64.6:

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

Если мы рассматриваем язык <tex>L</tex> как проблему, то проблема называется ''разрешимой'', если язык <tex>L</tex> ''рекурсивный''. В противном случае проблема называется ''неразрешимой''. Но часто данные понятия просто отождествляются.

{{Определение
|definition = Язык <tex>L</tex> называется '''разрешимым''', если существует такая [http://neerc.ifmo.ru/wiki/index.php?title=%D0%92%D1%8B%D1%87%D0%B8%D1%81%D0%BB%D0%B8%D0%BC%D1%8B%D0%B5_%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D0%B8 вычислимая] (англ. ''computable'') функция <tex>f : \Sigma^* \to \{0, 1\} : x \in L \Leftrightarrow f(x) = 1</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>.
}}

На словах, ''универсальный язык'' можно определить следующим образом:

''Универсальный язык'' {{---}} это язык всех пар "программа и её вход" таких, что программа на входе возвращает 1, входные данные программы и сама программа должны быть расположены над одним алфавитом.
Так как программа {{---}} это набор строк, занумеровав которые, можем получить биекцию "число" <tex>\to</tex> "строка"

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

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

{{Утверждение
|statement=
Множество всех рациональных чисел, меньших числа <tex>e</tex> (основания натуральных логарифмов) или <tex>\pi</tex>, разрешимо.
|proof=
Для чисел <tex>e, \pi</tex> существуют различные техники нахождения их точного представления, одна их которых описана в статье [http://www.mathpropress.com/stan/bibliography/spigot.pdf «A Spigot Algorithm for the Digits of Pi»]. Авторами алгоритма и его нарицателями являются американские математики Стенли Рабинович (Stanley Rabinowitz) и Стен Вэгон (Stan Wagon), которые создали свой алгоритм для нахождения цифр числа <tex>\pi</tex> в 1995 году. Сама же идея алгоритма вышла из-под пера некого Сейла (Sale) ещё в 1968 году, и предназначался тот алгоритм для нахождения цифр числа <tex>e</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 = 0;; ++i)
'''if''' (getDigit(<tex>e</tex>, i) > getDigit(<tex>r</tex>, i))
'''return''' 1
'''if''' (getDigit(<tex>e</tex>, i) < getDigit(<tex>r</tex>, i))
'''return''' 0
Так как число ''e'' иррационально (не существует его рационального представления), то ответ будет найден.
}}

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

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

Пусть язык <tex>U</tex> разрешим, тогда существует программа <tex> u </tex> : <tex> \forall \langle p, x \rangle \in U \Rightarrow u(\langle p, x \rangle) = 1</tex>, <tex> \forall \langle p, x \rangle \notin U \Rightarrow u(\langle p, x \rangle) = 0</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>.

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

== Источники информации ==
* Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 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 Википедия — Рекурсивный язык]
* [http://www.mathpropress.com/stan/bibliography/spigot.pdf «A Spigot Algorithm for the Digits of Pi»]

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

Ядро и образ линейного оператора

2014-04-17T06:27:20Z

188.162.64.6: /* Источники */

{{Определение
|definition=
Пусть <tex>\mathcal{A}: X \rightarrow Y</tex> {{---}} линейный оператор.<br>

'''Ядром''' линейного оператора <tex>\mathcal{A}</tex> называется множество <tex>~{Ker\mathcal{A}} = \{x\in X \mid \mathcal{A}x = 0 \}</tex>
}}

{{Определение
|definition=
Пусть <tex>\mathcal{A}: X \rightarrow Y</tex> {{---}} линейный оператор.<br>

'''Образом''' линейного оператора <tex>\mathcal{A}</tex> называется множество <tex>~{Im\mathcal{A}} = \{y\in Y \mid y = \mathcal{A}x \}</tex> ''(множество значений)''
}}

{{Лемма
|statement=Ядро и образ линейного оператора являются подпространствами линейных пространств <tex>X</tex> и <tex>Y</tex> соответственно.
}}

{{Теорема
|about=O ядре и базисе
|statement = <tex>\dim Ker\mathcal{A} + \dim Im\mathcal{A} = n = \dim X</tex>
|proof=
<tex>Ker\mathcal{A}</tex> {{---}} подпространство <tex>X</tex>

'''Шаг 1.''' Пусть <tex>\dim Ker\mathcal{A} = k;\ 0 \leqslant k \leqslant n</tex>

<tex>\{e\}_{i = 1}^{k}</tex> {{---}} базис <tex>Ker\mathcal{A}</tex> <tex>(\mathcal{8} e_i : \mathcal{A}e_i = 0\ (i = 1..k))</tex>

Дополним <tex>\{e\}_{i = 1}^{k}</tex> до базиса <tex>X</tex>, получим базис <tex>\{e\}_{i = 1}^{n}</tex>, где <tex>n = \dim X</tex>

'''Шаг 2.''' Докажем, что <tex>Im\mathcal{A}</tex> {{---}} линейная оболочка <tex>\{ \mathcal{A}e_{k+1}\ ...\ \mathcal{A}e_n \}</tex>

Рассмотрим <tex>X = \xi^1 e_1 + \xi^2 e_2 +\ ...\ + \xi^n e_n</tex>

<tex>\mathcal{A}x = 0 +\ ...\ + 0 + \mathcal{A}e_{k+1} +\ ...\ + \mathcal{A}e_n = y \in Im\mathcal{A}</tex>

'''Шаг 3.''' Осталось доказать следующее: <tex>\dim</tex> Л.О.<tex>\{\mathcal{A}e_{k+1}\ ...\ \mathcal{A}e_n\} = n - k = \dim Im\mathcal{A}</tex>

Докажем от противного.

Пусть <tex>\{\mathcal{A}e_{k+1}\ ...\ \mathcal{A}e_n\}</tex> {{---}} линейно зависимы <tex>\Rightarrow</tex> существует нетривиальная линейная комбинация, что <tex>\alpha_{k+1}\mathcal{A}e_{k+1} +\ ...\ + \alpha_n\mathcal{A}e_n = 0 \ (*)</tex>

Пусть <tex>z = \alpha_{k+1}e_{k+1} +\ ...\ + \alpha_{n}e_n</tex>

Рассмотрим <tex>\mathcal{A}z = \alpha_{k+1}\mathcal{A}e_{k+1} +\ ...\ + \alpha_n\mathcal{A}e_n = 0</tex> в соответствии с <tex>(*)</tex>

Получаем, что <tex>z \in Ker\mathcal{A} \Rightarrow z=\sum\limits_{i=1}^{k} \alpha_ie_i</tex>, что противоречит выбору <tex>z</tex>

Значит, <tex>\dim Im\mathcal{A} = n - k</tex>
}}

== Функции от линейного оператора ==

Пусть <tex>\mathcal{A} \colon X \to X</tex>

<tex>\mathcal{A}^n = \mathcal{A} \cdot\ ...\ \cdot \mathcal{A}</tex> (n раз)

<tex> p_m(\lambda) = \sum\limits_{j = 0}^m \alpha_j \lambda^j \longrightarrow p_m(\mathcal{A}) = \sum\limits_{j = 0}^m \alpha_j \mathcal{A}^j \ (\mathcal{A}^0 = J)</tex>

Если <tex>\mathcal{9} \mathcal{A}^{-1}</tex>, то переходим к квазиполиномам:
<tex>p_{m, k} = \sum\limits_{j = -k}^m \alpha_j \mathcal{A}^j</tex>

== Источники ==

* Анин конспект. Гы

[[Категория: Алгебра и геометрия 1 курс]]
[[Категория: Линейные операторы]]

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

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

Ядро и образ линейного оператора