Основная цель этой лекции - дать определения понятий,
необходимых для математически строгой формулировки
результатов следующих двух лекций.
Для более подробного
ознакомления с вычислимостью,
разрешимостью, перечислимостью
и универсальными моделями вычислений
следует обратиться к какому-либо вводному курсу
по теории алгоритмов,
например [30, с. 93-106, 109-121]
или [5,с. 8-20, 112-123].
В разделе 14.1
фиксируется конкретная модель вычислений -
машина Тьюринга и даются
определения
(недетерминированной) машины Тьюринга,
детерминированной машины Тьюринга
и вычислимой функции.
В разделе 14.2 определяются разрешимые и
перечислимые множества.
В разделе 14.3
вводятся термины
"массовая задача",
"индивидуальная задача",
"схема кодирования",
"задача распознавания",
"алгоритмическая проблема".
В 14.4*
формулируется теорема о соответствии
машин Тьюринга грамматикам типа 0,
а также теорема о нормальной форме для
грамматик типа 0.
В разделе 14.5
формулируется известная неразрешимая проблема -
проблема соответствий Поста.
На сведEнии именно к этой алгоритмической проблеме
основываются
все доказательства неразрешимости
в лекции 16,
где рассматриваются
алгоритмические проблемы,
связанные с контекстно-свободными
грамматиками.
Определение 14.1.1. Машиной Тьюринга
называется семерка$$M \peq \lalg Q , \Sigma , \Gamma , b_0 , \Delta , I , F \ralg ,$$
где Q, $$\Gamma $$ и $$\Delta $$ - конечные множества, $$\Sigma \subset \Gamma $$, $$b_0 \in \Gamma \sminus \Sigma $$, $$I \subseteq Q $$, $$F \subseteq Q $$
и$$\Delta \subseteq (( Q \sminus F ) \times \Gamma )
\times ( Q \times \Gamma \times \{ -1 , 0 , 1 \} ) .$$
Здесь Q - множество состояний $$\Sigma $$ - входной алфавит
( внешний алфавит ), $$\Gamma $$ - ленточный алфавит
(tape b0 - бланк
( пробел, пустой символ, blank symbol), $$\Delta $$ - множество переходов, I - множество начальных состояний, F - множество заключительных состояний.
Определение 14.1.2. Конфигурацией машины Тьюринга называется любая четверка $$\lp x , q , a , y \rp $$, где $$x \in \Gamma ^* $$, $$q \in Q $$, $$a \in \Gamma $$, $$y \in \Gamma ^* $$.
Определение 14.1.3.
Определим на множестве всех конфигураций машины Тьюринга M
бинарное отношение $$\myunderset{ M }{\vdash} $$
( такт работы )
следующим образом.
Если $$\lp \lp p , a \rp , \lp q , c , 0 \rp \rp \in \Delta $$, то$$\lp x , p , a , y \rp \myunderset{ M }{\vdash} \lp x , q , c , y \rp$$ для всех $$x \in \Gamma ^*$$ и $$y \in \Gamma ^* $$.
Если $$\lp \lp p , a \rp , \lp q , c , 1 \rp \rp \in \Delta $$, то$$\lp x , p , a , d y \rp \myunderset{ M }{\vdash} \lp x c , q , d , y \rp \rusand \lp x , p , a , \varepsilon \rp \myunderset{ M }{\vdash} \lp x c , q , b_0 , \varepsilon \rp$$ для всех $$x \in \Gamma ^* $$, $$y \in \Gamma ^*$$ и $$d \in \Gamma $$.
Если $$\lp \lp p , a \rp , \lp q , c , -1 \rp \rp \in \Delta $$, то$$\lp x d , p , a , y \rp \myunderset{ M }{\vdash} \lp x , q , d , c y \rp \rusand \lp \varepsilon , p , a , y \rp \myunderset{ M }{\vdash} \lp \varepsilon , q , b_0 , c y \rp$$ для всех $$x \in \Gamma ^* $$, $$y \in \Gamma ^*$$ и $$d \in \Gamma $$.
Замечание 14.1.4. Если из контекста ясно, о какой машине Тьюринга идет речь, вместо $$\myunderset{ M }{\vdash}$$ будем писать просто $$\vdash $$.
Определение 14.1.5. Как и для МП-автомата, для машины Тьюринга бинарное отношение $$\overstar{\vdash} $$ определяется как рефлексивное, транзитивное замыкание отношения $$\vdash $$.
Замечание 14.1.6. Если $$\lp x_1 , q_1 , a_1 , y_1 \rp \overstar{\vdash} \lp x_2 , q_2 , a_2 , y_2 \rp $$, то для любых $$k \in \mathbb{N} $$ и $$l \in \mathbb{N} $$ найдутся такие $$m \in \mathbb{N} $$ и $$n \in \mathbb{N} $$, что $$\lp b_0 ^k x_1 , q_1 , a_1 , y_1 b_0 ^l \rp \overstar{\vdash} \lp b_0 ^m x_2 , q_2 , a_2 , y_2 b_0 ^n \rp $$.
Замечание 14.1.7. Конфигурацию $$\lp b_0 ^m x , q , a , y b_0 ^n \rp $$ иногда изображают сокращенно $$x \underset{ q }{ a } y $$.
Замечание 14.1.8.
Машины Тьюринга можно изображать в виде диаграмм.
При этом каждое состояние обозначается кружком,
а переход - стрелкой.
Каждое начальное состояние распознается
по ведущей в него короткой стрелке.
Каждое заключительное состояние отмечается на диаграмме
двойным кружком.
Стрелка с пометкой a:ck,
ведущая из p в q,
показывает, что $$\lp \lp p , a \rp , \lp q , c , k \rp \rp $$
является переходом данной машины Тьюринга.
Обычно на диаграммах вместо чисел -1, 0, 1
(обозначающих движение влево, стояние на месте, движение вправо)
используются буквы L, N, R
соответственно.
Пример 14.1.9. Рассмотрим машину Тьюринга$$M \peq \lalg Q , \Sigma , \Gamma , b_0 , \Delta , I , F \ralg ,$$ где $$Q \peq \{ 0 , 1 , 2 , 3 \} $$, $$\Sigma \peq \{ a \} $$, $$\Gamma \peq \{ a , b \} $$, $$b_0 \peq b $$, $$I \peq \{ 0 \} $$, $$F \peq \{ 3 \} $$,$$\Delta \peq \{ \lp \lp 0 , b \rp \sqzcm \lp 1 , b , 1 \rp \rp \sqzcm \lp \lp 1 , a \rp \sqzcm \lp 2 , b , 1 \rp \rp \sqzcm \lp \lp 2 , a \rp \sqzcm \lp 1 , b , 1 \rp \rp \sqzcm \lp \lp 1 , b \rp \sqzcm \lp 3 , b , 0 \rp \rp \} .$$ $$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle \xymatrix { *=[o][F-]{0} \ar @`{+/l16mm/} [] ^{} \ar "1,2" ^{b:b\dr} *=[o][F-]{1} \ar "2,2" <0.6mm> ^{a:b\dr} \ar "1,3" ^{b:b\dn} *=[o][F=]{3} \\ % *=[o][F-]{2} \ar "1,2" <0.6mm> ^{a:b\dr} }$$ Можно проверить, что для любого $$k \in \mathbb{N} $$ выполняется следующее:$$\begin{align*} \underset{ 0 }{ b } a ^{k+1} \vdash \underset{ 1 }{ a } a ^k ,\\ \underset{ 1 }{ a } a ^{k+2} \overstar{\vdash} \underset{ 1 }{ a } a ^k ,\\ \underset{ 1 }{ a } a ^{2k+1} \overstar{\vdash} \underset{ 3 }{ b } . \end{align*}$$
Определение 14.1.10.
Машина Тьюринга$$\lalg Q , \Sigma , \Gamma , b_0 , \Delta , I , F \ralg$$
называется детерминированной,
если
множество I
содержит ровно один элемент
и
для каждой пары $$\lp p , a \rp \in ( Q \sminus F ) \times \Gamma $$
существует не более одной тройки $$\lp q , c , k \rp \in Q \times \Gamma \times \{ -1 , 0 , 1 \} $$
со свойством $$\lp \lp p , a \rp , \lp q , c , k \rp \rp \in \Delta $$.
Пример 14.1.11 Машина Тьюринга из примера 14.1.9 является детерминированной.
Определение 14.1.12.
Пусть f - частичная функция из $$\Sigma ^* $$
в $$\Sigma ^* $$.
Детерминированная машина Тьюринга$$M \peq \lalg Q , \Sigma , \Gamma , b_0 , \Delta , I , F \ralg$$
вычисляет
(computes)
функцию f
тогда и только тогда, когда
для каждого слова $$w \in \Sigma ^* $$
1) если f(w)
не определено,
то не существует таких $$p \in I $$, $$q \in F $$, $$a \in \Gamma $$, $$x \in \Gamma ^* $$, $$y \in \Gamma ^* $$,
что$$\lp \varepsilon , p , b_0 , w \rp
\overstar{\vdash} \lp x , q , a , y \rp ;$$
2) если f(w)=z,
то
для некоторых $$p \in I $$, $$q \in F $$, $$m \in \mathbb{N} $$
и $$n \in \mathbb{N} $$
выполнено условие$$\lp \varepsilon , p , b_0 , w \rp
\overstar{\vdash} \lp b_0 ^m , q , b_0 , z b_0 ^n \rp .$$
Определение 14.1.13. Частичная функция из $$\Sigma ^* $$ в $$\Sigma ^* $$ называется вычислимой, если существует детерминированная машина Тьюринга, вычисляющая эту функцию.
Пример 14.1.14. Машина Тьюринга из примера 14.1.9 вычисляет следующую частичную функцию:$$f( a ^n ) = \begin{cases} \varepsilon , \text{если число $ n $ четно,} \\ \text{не определено,} \text{если число $ n $ нечетно.} \end{cases}$$
Пример 14.1.15. Рассмотрим детерминированную машину Тьюринга$$\lalg Q , \Sigma , \Gamma , b_0 , \Delta , I , F \ralg ,$$ где$$\begin{align*} Q = \{ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 \} ,\\ \Sigma = \{ a \} ,\\ \Gamma = \{ a , b \} ,\\ b_0 = b ,\\ I = \{ 1 \} ,\\ F = \{ 7 \} ,\\ \Delta = \{ \lp \lp 1 , b \rp , \lp 2 , b , 1 \rp \rp ,\ \\ \hphantom{ {} = {} \{ } %\} \lp \lp 2 , b \rp , \lp 7 , b , 0 \rp \rp ,\ \lp \lp 2 , a \rp , \lp 3 , a , -1 \rp \rp ,\ \\ \hphantom{ {} = {} \{ } %\} \lp \lp 3 , b \rp , \lp 3 , a , 1 \rp \rp ,\ \lp \lp 3 , a \rp , \lp 4 , b , 1 \rp \rp ,\ \\ \hphantom{ {} = {} \{ } %\} \lp \lp 4 , b \rp , \lp 5 , b , -1 \rp \rp ,\ \lp \lp 4 , a \rp , \lp 8 , a , 0 \rp \rp ,\ \\ \hphantom{ {} = {} \{ } %\} \lp \lp 5 , b \rp , \lp 6 , b , -1 \rp \rp ,\ \\ \hphantom{ {} = {} \{ } %\} \lp \lp 6 , a \rp , \lp 6 , a , -1 \rp \rp ,\ \lp \lp 6 , b \rp , \lp 7 , b , 0 \rp \rp ,\ \\ \hphantom{ {} = {} \{ } %\} \lp \lp 8 , b \rp , \lp 8 , b , 1 \rp \rp ,\ \lp \lp 8 , a \rp , \lp 9 , a , 1 \rp \rp ,\ \\ \hphantom{ {} = {} \{ } %\} \lp \lp 9 , a \rp , \lp 9 , a , 1 \rp \rp ,\ \lp \lp 9 , b \rp , \lp 10 , b , -1 \rp \rp ,\ \\ \hphantom{ {} = {} \{ } %\} \lp \lp 10 , a \rp , \lp 11 , b , -1 \rp \rp ,\ \\ \hphantom{ {} = {} \{ } %\} \lp \lp 11 , b \rp , \lp 11 , b , 0 \rp \rp ,\ \lp \lp 11 , a \rp , \lp 12 , b , -1 \rp \rp ,\ \\ \hphantom{ {} = {} \{ } %\} \lp \lp 12 , a \rp , \lp 12 , a , -1 \rp \rp ,\ \lp \lp 12 , b \rp , \lp 13 , b , -1 \rp \rp ,\ \\ \hphantom{ {} = {} \{ } %\} \lp \lp 13 , b \rp ,\! \lp 13 , b , -1 \rp \rp ,\ \lp \lp 13 , a \rp ,\! \lp 14 , b , -1 \rp \rp ,\ \\ \hphantom{ {} = {} \{ } %\} \lp \lp 14 , a \rp ,\! \lp 8 , a , 1 \rp \rp ,\ \lp \lp 14 , b \rp ,\! \lp 3 , b , 1 \rp \rp \} . \end{align*}$$ $$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle \xymatrix { % *=[o][F=]{7} *=[o][F-]{6} \rloop{0,-1} ^{a:a\dl} \ar "1,2" _{b:b\dn} *=[o][F-]{5} \ar "1,3" _{b:b\dl} \\ % *=[o][F-]{1} \ar @`{+/l16mm/} [] ^{} \ar "2,3" ^{b:b\dr} *=[o][F-]{2} \ar "1,2" ^*!/u1.5mm/{b:b\dn} \ar "3,2" ^*!/u2mm/{a:a\dl} \\ % *=[o][F-]{3} \rloop{0,1} ^{b:a\dr} \ar "3,4" ^{a:b\dr} *=[o][F-]{4} \ar "1,4" _{b:b\dl} \ar "3,5" ^{a:a\dn} *=[o][F-]{8} \rloop{0,1} ^{b:b\dr} \ar "3,6" ^{a:a\dr} *=[o][F-]{9} \rloop{0,1} ^{a:a\dr} \ar "4,5" ^{b:b\dl} \\ *=[o][F-]{14} \ar "3,5" <-0.2mm> ^-(.3){a:a\dr} \ar "3,2" ^{b:b\dr} *=[o][F-]{13} \rloop{0,-1} ^{b:b\dl} \ar "4,1" ^{a:b\dl} *=[o][F-]{12} \rloop{0,-1} ^{a:a\dl} \ar "4,2" ^{b:b\dl} *=[o][F-]{11} \rloop{0,-1} ^{b:b\dn} \ar "4,3" ^{a:b\dl} *=[o][F-]{10} \ar "4,4" ^{a:b\dl} }$$ Можно проверить, что для любых $$i \in \mathbb{N} $$, $$j \in \mathbb{N} $$ и $$k \in \mathbb{N} $$ выполняется следующее:$$\begin{align*} \underset{ 1 }{ b } a ^{k+2} \overstar{\vdash} a b \underset{ 8 }{ a } a ^k ,\\ a b ^{j+1} \underset{ 8 }{ a } a ^2 \overstar{\vdash} \underset{ 7 }{ b } a ^{j+2} ,\\ a b ^{j+1} \underset{ 8 }{ a } a ^{k+3} \overstar{\vdash} a ^{j+2} b \underset{ 8 }{ a } a ^k ,\\ a ^{i+2} b ^{j+1} \underset{ 8 }{ a } a ^{k+2} \overstar{\vdash} a ^{i+1} b ^{j+2} \underset{ 8 }{ a } a ^k ,\\ a b ^{j+1} \underset{ 8 }{ a } a ^{k+2j+5} \overstar{\vdash} a b ^{j+2} \underset{ 8 }{ a } a ^k . \end{align*}$$ Следовательно,$$\begin{align*} \underset{ 1 }{ b } a ^{i+(j+2)^2} \squeeze{\overstar{\vdash}} a b ^{j+1} \underset{ 8 }{ a } a ^{i+2} ,\\ \underset{ 1 }{ b } a ^{(k+2)^2} \overstar{\vdash} \underset{ 7 }{ b } a ^{k+2} . \end{align*}$$ Рассматриваемая машина Тьюринга вычисляет следующую частичную функцию:$$f( a ^n ) = \begin{cases} a^{\sqrt{n}} , \text{если $ \sqrt{n} \in \mathbb{N} $,} \\ \text{не определено,} \text{если $ \sqrt{n} \notin \mathbb{N} $.} \end{cases}$$
Замечание 14.1.16. Тезисом Черча-Тьюринга (а иногда просто тезисом Черча ) называется следующее неформальное утверждение: для каждой вычислимой в интуитивном смысле частичной функции из $$\Sigma ^* $$ в $$\Sigma ^* $$ существует машина Тьюринга, которая эту функцию вычисляет.
Упражнение 14.1.17.
Найти детерминированную машину Тьюринга
с входным алфавитом {a},
вычисляющую функцию f,
заданную соотношением
f(an) = an+1.
Упражнение 14.1.18.
Найти детерминированную машину Тьюринга
с входным алфавитом {a},
вычисляющую функцию f,
заданную соотношением$$f(a^n) = \varepsilon .$$
Определение 14.1.19.
Зафиксируем два различных символа a и b
и положим $$\Sigma = \{a,b\} $$.
Пусть k -
положительное целое число
и f -
частичная функция из $$\mathbb{N}^k $$
в $$\mathbb{N} $$.
Детерминированная машина Тьюринга$$M \peq \lalg Q , \Sigma , \Gamma , b , \Delta , I , F \ralg$$
вычисляет
функцию f
тогда и только тогда, когда
для любых натуральных чисел $$n_1 , \ldots , n_k $$
выполняются следующие условия:
1) если $$f ( n_1 , \ldots , n_k ) $$ не определено, то не существует таких $$p \in I $$, $$q \in F $$, $$a \in \Gamma $$, $$x \in \Gamma ^* $$, $$y \in \Gamma ^* $$, что$$\lp \varepsilon , p , b , a^{n_1} b a^{n_2} b \ldots b a^{n_k} \rp \overstar{\vdash} \lp x , q , a , y \rp ;$$
2) если $$f ( n_1 , \ldots , n_k ) = l $$, то для некоторых $$p \in I $$, $$q \in F $$, $$m \in \mathbb{N} $$ и $$n \in \mathbb{N} $$ выполнено условие$$\lp \varepsilon , p , b , a^{n_1} b a^{n_2} b \ldots b a^{n_k} \rp \overstar{\vdash} \lp b ^m , q , b_0 , a^l b ^n \rp .$$
Упражнение 14.1.20. Рассмотрим детерминированную машину Тьюринга, изображенную на рисунке.$$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle \xymatrix { *=[o][F-]{1} \ar @`{+/l16mm/} [] ^{} \ar "1,2" ^{b:b\dr} *=[o][F-]{2} \ar "1,3" ^{a:b\dr} \ar "2,3" _{b:b\dn} *=[o][F-]{3} \ar "1,4" ^{a:b\dr} \ar "2,3" ^{b:b\dn} *=[o][F-]{4} \ar "1,5" ^{a:b\dr} \ar "2,3" ^{b:b\dn} *=[o][F-]{5} \rloop{0,1} ^{a:b\dr} \ar "2,5" ^{b:b\dn} \\ % *=[o][F=]{6} *=[o][F=]{7} }$$ Какую функцию из $$\mathbb{N} $$ в $$\mathbb{N} $$ она вычисляет?
Упражнение 14.1.21. Рассмотрим детерминированную машину Тьюринга, изображенную на рисунке.$$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle \xymatrix { % *=[o][F-]{6} \rloop{0,1} ^{b:b\dr} \ar "1,3" ^{a:a\dr} *=[o][F-]{7} \rloop{0,1} ^{a:a\dr} \ar "2,3" ^{b:a\dl} *=[o][F-]{1} \ar @`{+/l16mm/} [] ^{} \ar "1,6" ^{b:a\dr} *=[o][F-]{2} \rloop{0,1} ^{a:a\dr} \ar "1,7" ^{b:b\dr} *=[o][F-]{3} \rloop{0,1} ^{a:b\dr} \ar @/^4mm/ "3,2" ^{b:a\dl} \\ % *=[o][F-]{8} \rloop{0,-1} ^{a:a\dl} \ar "3,2" _{b:b\dl} \\ *=[o][F-]{5} \ar "1,2" ^{a:a\dr} \ar "4,2" _{b:b\dr} *=[o][F-]{4} \rloop{0,-1} ^{b:b\dl} \ar "3,1" _{a:b\dl} *=[o][F-]{10} \ar "4,7" ^{b:a\dr} \\ % *=[o][F-]{9} \rloop{0,-1} ^{a:b\dl} \ar "3,5" ^{b:b\dr} *=[o][F-]{15} \rloop{0,-1} ^{a:a\dl} \ar "4,5" ^{b:a\dr} *=[o][F-]{16} \rloop{0,1} ^{a:a\dr} \ar "4,7" ^{b:b\dr} *=[o][F-]{11} \rloop{0,1} ^{b:b\dr} \ar "5,6" ^{a:a\dl} \\ % *=[o][F-]{14} \rloop{0,-1} ^{b:b\dl} \ar "4,3" ^(0.3){a:a\dl} *=[o][F-]{13} \ar "5,4" ^{b:b\dl} \ar "6,4" ^{a:b\dl} *=[o][F-]{12} \ar "5,5" ^{b:a\dl} \ar "6,7" ^(0.3){a:b\dr} \\ % *=[o][F-]{17} \ar "4,2" ^{a:b\dl} \ar "6,7" ^{b:b\dr} *=[o][F-]{18} \rloop{0,1} ^{b:b\dr} \ar "7,7" ^{a:b\dn} \\ % *=[o][F=]{19} }$$ Какую функцию из $$\mathbb{N} \times \mathbb{N} $$ в $$\mathbb{N} $$ она вычисляет?
Определение 14.2.1.
Говорят, что детерминированная машина Тьюринга$$\lalg Q , \Sigma , \Gamma , b_0 , \Delta ,
\{ \qinitial \} , \{ \qaccept , \qreject \} \ralg$$
с выделенным состоянием qa разрешает
(decides) язык $$L \subseteq \Sigma ^* $$,
если
1) для каждого слова $$w \in L $$ найдутся такие $$m \in \mathbb{N} $$ и $$n \in \mathbb{N} $$, что $$\lp \varepsilon , \qinitial , b_0 , w \rp \overstar{\vdash} \lp b_0 ^m , \qaccept , b_0 , b_0 ^n \rp $$ ;
2) для каждого слова $$w \in \Sigma ^* \sminus L $$
найдутся такие $$m \in \mathbb{N} $$
и $$n \in \mathbb{N} $$,
что $$\lp \varepsilon , \qinitial , b_0 , w \rp \overstar{\vdash} \lp b_0 ^m , \qreject , b_0 , b_0 ^n \rp $$.
Состояние qa
называется допускающим
( принимающим, accept state),
состояние qr
называется отвергающим
( непринимающим, (
Пример 14.2.2. Рассмотрим детерминированную машину Тьюринга$$M \peq \lalg Q , \Sigma , \Gamma , b_0 , \Delta , \{ \qinitial \} , \{ \qaccept , \qreject \} \ralg ,$$ где $$Q = \{ 0 , 1 , 2 , 3 , 4 , 5 \} $$, $$\Sigma = \{ a \} $$, $$\Gamma = \{ a , b \} $$, $$b_0 = b $$, $$\qinitial = 0 $$, $$\qaccept = 4 $$, $$\qreject = 5 $$ и$$\begin{align*} {} \Delta = \{ \lp \lp 0 , b \rp , \lp 1 , b , 1 \rp \rp ,\ \\ \hphantom{ {} = {} \{ } %\} \lp \lp 1 , a \rp , \lp 2 , b , 1 \rp \rp ,\ \lp \lp 2 , a \rp , \lp 3 , b , 1 \rp \rp ,\ \lp \lp 3 , a \rp , \lp 1 , b , 1 \rp \rp ,\ \\ \hphantom{ {} = {} \{ } %\} \lp \lp 1 , b \rp , \lp 4 , b , 0 \rp \rp ,\ \lp \lp 2 , b \rp , \lp 5 , b , 0 \rp \rp ,\ \lp \lp 3 , b \rp , \lp 5 , b , 0 \rp \rp \} . \end{align*}$$ $$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle \xymatrix { *=[o][F-]{0} \ar @`{+/l16mm/} [] ^{} \ar "1,2" ^{b:b\dr} *=[o][F-]{1} \ar "1,3" ^{a:b\dr} \ar "2,2" ^{b:b\dn} *=[o][F-]{2} \ar "1,4" ^{a:b\dr} \ar "2,4" _{b:b\dn} *=[o][F-]{3} \ar `ul^l{+/u7mm/}`l^dl{[0,-2]}_{a:b\dr} "1,2" \ar "2,4" ^{b:b\dn} \\ % *=[o][F=]{4} *=[o][F=]{5} }$$ Эта машина Тьюринга разрешает язык $$\{ a^{3n} \mid n \in \mathbb{N} \} $$.
Определение 14.2.3.
Язык L
над алфавитом $$\Sigma $$
называется разрешимым
или рекурсивным (decidable, recursive),
если
существует детерминированная машина Тьюринга$$\lalg Q , \Sigma , \Gamma , b_0 , \Delta ,
\{ \qinitial \} , \{ \qaccept , \qreject \} \ralg$$
(с выделенным состоянием qa ),
которая разрешает язык L.
Определение 14.2.4. Говорят, что машина Тьюринга$$M \peq \lalg Q , \Sigma , \Gamma , b_0 , \Delta , \{ \qinitial \} , \{ \qaccept \} \ralg$$ допускает ( принимает, accepts) слово $$w \in \Sigma ^* $$, если для некоторых $$m \in \mathbb{N} $$ и $$n \in \mathbb{N} $$ $$\lp \varepsilon , \qinitial , b_0 , w \rp \overstar{\vdash} \lp b_0 ^m , \qaccept , b_0 , b_0 ^n \rp $$.
Определение 14.2.5.
Язык, допускаемый
машиной Тьюринга M, -
это язык, состоящий из всех допускаемых данной машиной Тьюринга слов.
Определение 14.2.6. Язык называется перечислимым ( рекурсивно перечислимым, полуразрешимым, recursively enumerable), если существует детерминированная машина Тьюринга, допускающая этот язык.
Замечание 14.2.7. В определении 14.2.6 можно отбросить требование детерминированности машины Тьюринга.
Теорема 14.2.8. Каждый разрешимый язык является перечислимым.
Доказательство.
Пусть дана машина Тьюринга$$M \peq \lalg Q , \Sigma , \Gamma , b_0 , \Delta ,
\{ \qinitial \} , \{ \qaccept , \qreject \} \ralg$$
с выделенным состоянием qa,
которая разрешает язык $$L \subseteq \Sigma ^* $$.
Тогда машина Тьюринга$$M' \peq \lalg Q , \Sigma , \Gamma , b_0 , \Delta ,
\{ \qinitial \} , \{ \qaccept \} \ralg$$
допускает язык L.
Пример 14.2.9. Если в машине Тьюринга из примера 14.1.15 заменить переход $$\lp \lp 6 , a \rp , \lp 6 , a , -1 \rp \rp $$ на $$\lp \lp 6 , a \rp , \lp 6 , b , -1 \rp \rp $$, то получится машина Тьюринга, допускающая язык $$\{ a^{n^2} \mid n \in \mathbb{N} \} $$. Следовательно, этот язык является перечислимым. Можно доказать, что он даже является разрешимым.
Теорема 14.2.10. Существует такая машина Тьюринга над однобуквенным алфавитом $$\Sigma = \{ a \} $$, что язык, допускаемый этой машиной Тьюринга, неразрешим.
Доказательство. Доказательство существования перечислимого неразрешимого множества можно найти, например, в [31, 9.2].
Упражнение 14.2.11.
Найти детерминированную машину Тьюринга
с входным алфавитом {a},
разрешающую язык $$\{ a^{n} \mid n \leq 2 \} $$.
Упражнение 14.2.12.
Найти детерминированную машину Тьюринга
с входным алфавитом {a},
допускающую язык $$\{ a^{3n+2} \mid n \geq 0 \} $$
Определение 14.3.1. Массовой задачей
(problem)
называется
бесконечная серия "однотипных" индивидуальных задач
(instance),
каждая из которых имеет определенный ответ.
С каждой массовой задачей связана некоторая фиксированная схема кодирования
(
Определение 14.3.2. Задачей распознавания (decision problem) называется массовая задача, в которой ответами индивидуальных задач могут быть только "да" и "нет" (то есть существует только два возможных ответа).
Пример 14.3.3.
Зафиксируем некоторый алфавит $$\Sigma $$.
Рассмотрим следующие однотипные индивидуальные задачи:
даны два слова $$x \in \Sigma ^* $$
и $$y \in \Sigma ^* $$,
необходимо выяснить, является ли
слово x
подсловом слова y.
Пусть # -
новый символ, не принадлежащий алфавиту $$\Sigma $$.
Кодом индивидуальной задачи про конкретные
слова x и y
будем считать слово x#y
в алфавите $$\Sigma \cup \{ \# \} $$.
Эта массовая задача является задачей распознавания.
Определение 14.3.4. Алгоритмическая проблема -
проблема, в которой требуется найти алгоритм для решения
массовой задачи.
Если такой алгоритм существует, то данная проблема называется алгоритмически разрешимой
или просто разрешимой (decidable,
Замечание 14.3.5.
Алгоритмическая проблема,
относящаяся к некоторой задаче распознавания,
алгоритмически разрешима
тогда и только тогда, когда
Пример 14.3.6. Рассмотрим массовую задачу из примера 14.3.3. Соответствующая алгоритмическая проблема разрешима, так как разрешим язык $$\{ x \# u x v \mid x \in \Sigma ^* ,\ u \in \Sigma ^* \commaand v \in \Sigma ^* \} $$.
Пример 14.3.7. Зафиксируем некоторый алфавит $$\Sigma $$. Рассмотрим следующие однотипные индивидуальные задачи: дана порождающая грамматика$$G = \lalg \{ A_1 , \ldots , A_n \} , \Sigma , P , A_1 \ralg ,$$ необходимо выяснить, является ли эта грамматика праволинейной.
Для полной строгости необходимо договориться, как
кодировать грамматику G
в виде слова.
Например, можно использовать алфавит $$\Sigma \cup \{ \heartsuit , \spadesuit , 0 , 1 \} $$,
где $$\heartsuit $, $ \spadesuit $, $ 0 $, $ 1 $$ -
дополнительные символы, не принадлежащие множеству $$\Sigma $$.
Вспомогательный символ Ai
заменим на слово, состоящее из
символа $$\heartsuit $$
и кода числа i
в двоичной системе счисления.
В каждом правиле $$\alpha \tto \beta $$
добавим символ $$\spadesuit $$
на месте $$\to $$
и после слова $$\beta $$.
Кодом грамматики G
будем считать результат конкатенации кодов всех правил
из множества P.
Например, грамматика$$\begin{align*}
A_1 \; {\to} \; a , \\
A_1 \; {\to} \; A_2 A_1 , \\
A_2 \; {\to} \; a A_3 , \\
A_3 \; {\to} \; \varepsilon , \\
A_3 \; {\to} \; b A_1
\end{align*}$$
(над алфавитом $$\Sigma = \{ a , b \} $$ )
кодируется словом$$\heartsuit 1 \spadesuit
a \spadesuit
\heartsuit 1 \spadesuit
\heartsuit 1 0 \heartsuit 1 \spadesuit
\heartsuit 1 0 \spadesuit
a \heartsuit 1 1 \spadesuit
\heartsuit 1 1 \spadesuit
\spadesuit
\heartsuit 1 1 \spadesuit
b \heartsuit 1 \spadesuit .$$
Легко понять, что соответствующая алгоритмическая проблема (проблема проверки праволинейности) разрешима.
Упражнение 14.3.8.
Разрешима ли алгоритмическая проблема распознавания
четности длины слова над алфавитом {a,b}?
Теорема 14.4.1. Класс языков, порождаемых грамматиками типа 0, совпадает с классом перечислимых языков.
Доказательство можно найти, например, в [СерГал с. 24-26].
Упражнение 14.4.2.
Выводимо ли слово aab
в грамматике$$\begin{align*}
S \; {\to} \; S b , T a \; {\to} \; a a T , \\
S \; {\to} \; S T , T b \; {\to} \; a b , \\
S \; {\to} \; S U , U a a a \; {\to} \; a a U , \\
S \; {\to} \; \varepsilon , U a b \; {\to} \; b ?
\end{align*}$$
Упражнение 14.4.3.
Выводимо ли слово aaaaaaaab
в грамматике$$\begin{align*}
S \; {\to} \; S b , T a \; {\to} \; a a T , \\
S \; {\to} \; S T , T b \; {\to} \; a b , \\
S \; {\to} \; S U , U a a a \; {\to} \; a a U , \\
S \; {\to} \; \varepsilon , U a b \; {\to} \; b ?
\end{align*}$$
Замечание 14.4.4.
Неизвестно,
порождает ли грамматика$$\begin{align*}
R \; {\to} \; Ra , Ta \; {\to} \; aaT , \\
R \; {\to} \; S , Tb \; {\to} \; ab , \\
S \; {\to} \; Sb , Uaaa \; {\to} \; aaU , \\
S \; {\to} \; ST , Uab \; {\to} \; b \\
S \; {\to} \; SU , \\
S \; {\to} \; \varepsilon ,
\end{align*}$$
все слова в алфавите {a,b}.
Упражнение 14.4.5.
Пусть $$\Sigma = \{ a , b , c , d , e \} $$.
Рассмотрим грамматику$$\begin{align*}
R \; {\to} \; ccdcdcddccddcdccca , ce \; {\to} \; eca , \\
ac \; {\to} \; ca , eca \; {\to} \; ce , \\
ca \; {\to} \; ac , de \; {\to} \; edb , \\
bc \; {\to} \; cb , edb \; {\to} \; de , \\
cb \; {\to} \; bc , cca \; {\to} \; ccae , \\
ad \; {\to} \; da , ccae \; {\to} \; cca . \\
da \; {\to} \; ad , \\
bd \; {\to} \; db , \\
db \; {\to} \; bd ,
\end{align*}$$
Выводимо ли в ней слово ccdcdcddccddcdcccabba?
Упражнение 14.4.6. Является ли разрешимым язык, порождаемый грамматикой$$\begin{align*} S \; {\to} \; c S , ac \; {\to} \; ca , cdc \; {\to} \; cdc R , \\ S \; {\to} \; d S , ca \; {\to} \; ac , R cca \; {\to} \; cc R , \\ S \; {\to} \; aa , bc \; {\to} \; cb , R ddb \; {\to} \; dd R , \\ cb \; {\to} \; bc , R cdd \; {\to} \; cdd T , \\ ad \; {\to} \; da , T cc \; {\to} \; cca T , \\ da \; {\to} \; ad , T dd \; {\to} \; ddb T , \\ bd \; {\to} \; db , T cdc \; {\to} \; cdc ? \\ db \; {\to} \; bd , \end{align*}$$
Определение 14.4.7. Порождающая грамматика в нормальной форме - это порождающая грамматика, в которой каждое правило имеет вид $$A \to a $$, $$A \to B C $$ или $$A B \to \varepsilon $$, где $$A \in N $$, $$B \in N $$, $$C \in N $$, $$a \in \Sigma $$.
Теорема 14.4.8. Каждая порождающая грамматика эквивалентна некоторой порождающей грамматике в нормальной форме.
Упражнение 14.4.9.
Существует ли такая порождающая грамматика G,
что язык $$L(G) \sminus \{ \varepsilon \} $$
не порождается ни одной грамматикой типа 0?
Определение 14.5.1. Постовской системой соответствия
над алфавитом $$\Sigma $$
называется упорядоченная
пара конечных последовательностей $$(( x_1 , \ldots , x_n ) , ( y_1 , \ldots , y_n )) $$,
где $$x_i \in \Sigma ^* $$
и $$y_i \in \Sigma ^* $$
для всех i.
Замечание 14.5.2. Систему $$(( x_1 , \ldots , x_n ) , ( y_1 , \ldots , y_n )) $$ иногда изображают в виде$$\domino{x_1}{y_1} , \ldots , \domino{x_n}{y_n} .$$
Определение 14.5.3. Решением (match)
постовской системы соответствия ((x1,...,xn),(y1,...,yn))
называется непустая последовательность индексов $$(i_1 , \ldots , i_k) $$,
удовлетворяющая условию$$x_{i_1} \ldots x_{i_k} = y_{i_1} \ldots y_{i_k} ,$$
где $$1 \leq i_j \leq n $$
для каждого j.
Пример 14.5.4.
Пусть $$\Sigma = \{ a , b , c \} $$.
Рассмотрим постовскую систему соответствия$$\domino{ a a b }{ a } ,
\domino{ a }{ a a } ,
\domino{ c a a }{ b c } .$$
Последовательность (2,1,3,2,2)
является решением этой системы,
так как$$a \cdot aab \cdot caa \cdot a \cdot a =
aa \cdot a \cdot bc \cdot aa \cdot aa .$$
Упражнение 14.5.5. Пусть $$\Sigma = \{ a , b , c , 0 , 1 , \diamondsuit , \heartsuit, \spadesuit \} $$. Существует ли решение у постовской системы соответствия$$\begin{gathered*} \domino{ a \spadesuit } { a \spadesuit a b a \heartsuit 1 a c a \spadesuit a } , \domino{ a b }{ b a } , \domino{ a c }{ c a } , \domino{ a \spadesuit }{ \spadesuit a } , \domino{ a \spadesuit }{ b a \spadesuit a } , \domino{ a \spadesuit }{ \spadesuit a b a } , \\ \!\domino{ a \heartsuit 1 a b }{ \diamondsuit a }\! , \!\domino{ a \heartsuit 1 a c }{ c a \heartsuit 1 0 a }\! , \!\domino{ a b a \heartsuit 1 0 a b }{ \heartsuit 1 0 a b a c a }\! , \!\domino{ a c a \heartsuit 1 0 a b }{ \heartsuit 1 0 a c a c a }\! , \!\domino{ a \heartsuit 1 0 a c }{ c a \heartsuit 1 1 a }\! , \!\domino{ a \heartsuit 1 1 a c }{ c a \heartsuit 1 a }\! , \\ \domino{ a \diamondsuit a b }{ \diamondsuit a } , \domino{ a \diamondsuit a c }{ \diamondsuit a } , \domino{ a b a \diamondsuit }{ \diamondsuit a } , \domino{ a c a \diamondsuit }{ \diamondsuit a } , \domino{ a \diamondsuit a \spadesuit a \spadesuit }{ \spadesuit } ? \end{gathered*}$$
Определение 14.5.6. Проблемой соответствий Поста (Post correspondence problem) называется проблема нахождения алгоритма, выясняющего для каждой постовской системы соответствия, существует ли решение этой системы.
Теорема 14.5.7. Пусть $$| \Sigma | \geq 2 $$. Тогда не существует алгоритма, позволяющего по произвольной постовской системе соответствия над алфавитом $$\Sigma $$ узнать, имеет ли она решение. ( Другими словами, проблема соответствий Поста неразрешима.)
Доказательство можно найти в [ХопМот, 9.4].
Упражнение 14.5.8. Существует ли решение у постовской системы соответствия $$\domino{ab}{abab} , \domino{b}{a} , \domino{aba}{b} , \domino{aa}{a} $$?
Упражнение 14.5.9. Существует ли решение у постовской системы соответствия $$\domino{b}{ca}, \domino{a}{ab}, \domino{ca}{a}, \domino{abc}{c} $$?
Упражнение 14.5.10. Существует ли решение у постовской системы соответствия $$\domino{a}{ab}, \domino{ca}{cc}, \domino{bcc}{ccca}, \domino{b}{ab} $$?
Упражнение 14.5.11. Существует ли решение у постовской системы соответствия $$\domino{ab}{aba}, \domino{b}{a}, \domino{aba}{b}, \domino{bbab}{abb} $$?
Упражнение 14.5.12. Существует ли решение у постовской системы соответствия $$\domino{ab}{b}, \domino{b}{bba}, \domino{ba}{b}, \domino{b}{bab}, \domino{b}{abb} $$?
Упражнение 14.5.13. Существует ли решение у постовской системы соответствия $$\domino{ab}{b}, \domino{b}{bba}, \domino{ba}{b}, \domino{aba}{aba} $$?
Упражнение 14.5.14. Существует ли решение у постовской системы соответствия $$\domino{a}{aaa}, \domino{\varepsilon}{aaaaa}, \domino{aaaaa}{aa} $$?
Упражнение 14.5.15. Существует ли постовская система соответствия, имеющая ровно одно решение?
Основная цель этой лекции - дать определения понятий,
необходимых для математически строгой формулировки
результатов следующих двух лекций.
Для более подробного
ознакомления с вычислимостью,
разрешимостью, перечислимостью
и универсальными моделями вычислений
следует обратиться к какому-либо вводному курсу
по теории алгоритмов,
например [30, с. 93-106, 109-121]
или [5,с. 8-20, 112-123].
В разделе 14.1
фиксируется конкретная модель вычислений -
машина Тьюринга и даются
определения
(недетерминированной) машины Тьюринга,
детерминированной машины Тьюринга
и вычислимой функции.
В разделе 14.2 определяются разрешимые и
перечислимые множества.
В разделе 14.3
вводятся термины
"массовая задача",
"индивидуальная задача",
"схема кодирования",
"задача распознавания",
"алгоритмическая проблема".
В 14.4*
формулируется теорема о соответствии
машин Тьюринга грамматикам типа 0,
а также теорема о нормальной форме для
грамматик типа 0.
В разделе 14.5
формулируется известная неразрешимая проблема -
проблема соответствий Поста.
На сведEнии именно к этой алгоритмической проблеме
основываются
все доказательства неразрешимости
в лекции 16,
где рассматриваются
алгоритмические проблемы,
связанные с контекстно-свободными
грамматиками.
Определение 14.1.1. Машиной Тьюринга
называется семерка$$M \peq \lalg Q , \Sigma , \Gamma , b_0 , \Delta , I , F \ralg ,$$
где Q, $$\Gamma $$ и $$\Delta $$ - конечные множества, $$\Sigma \subset \Gamma $$, $$b_0 \in \Gamma \sminus \Sigma $$, $$I \subseteq Q $$, $$F \subseteq Q $$
и$$\Delta \subseteq (( Q \sminus F ) \times \Gamma )
\times ( Q \times \Gamma \times \{ -1 , 0 , 1 \} ) .$$
Здесь Q - множество состояний $$\Sigma $$ - входной алфавит
( внешний алфавит ), $$\Gamma $$ - ленточный алфавит
(tape b0 - бланк
( пробел, пустой символ, blank symbol), $$\Delta $$ - множество переходов, I - множество начальных состояний, F - множество заключительных состояний.
Определение 14.1.2. Конфигурацией машины Тьюринга называется любая четверка $$\lp x , q , a , y \rp $$, где $$x \in \Gamma ^* $$, $$q \in Q $$, $$a \in \Gamma $$, $$y \in \Gamma ^* $$.
Определение 14.1.3.
Определим на множестве всех конфигураций машины Тьюринга M
бинарное отношение $$\myunderset{ M }{\vdash} $$
( такт работы )
следующим образом.
Если $$\lp \lp p , a \rp , \lp q , c , 0 \rp \rp \in \Delta $$, то$$\lp x , p , a , y \rp \myunderset{ M }{\vdash} \lp x , q , c , y \rp$$ для всех $$x \in \Gamma ^*$$ и $$y \in \Gamma ^* $$.
Если $$\lp \lp p , a \rp , \lp q , c , 1 \rp \rp \in \Delta $$, то$$\lp x , p , a , d y \rp \myunderset{ M }{\vdash} \lp x c , q , d , y \rp \rusand \lp x , p , a , \varepsilon \rp \myunderset{ M }{\vdash} \lp x c , q , b_0 , \varepsilon \rp$$ для всех $$x \in \Gamma ^* $$, $$y \in \Gamma ^*$$ и $$d \in \Gamma $$.
Если $$\lp \lp p , a \rp , \lp q , c , -1 \rp \rp \in \Delta $$, то$$\lp x d , p , a , y \rp \myunderset{ M }{\vdash} \lp x , q , d , c y \rp \rusand \lp \varepsilon , p , a , y \rp \myunderset{ M }{\vdash} \lp \varepsilon , q , b_0 , c y \rp$$ для всех $$x \in \Gamma ^* $$, $$y \in \Gamma ^*$$ и $$d \in \Gamma $$.
Замечание 14.1.4. Если из контекста ясно, о какой машине Тьюринга идет речь, вместо $$\myunderset{ M }{\vdash}$$ будем писать просто $$\vdash $$.
Определение 14.1.5. Как и для МП-автомата, для машины Тьюринга бинарное отношение $$\overstar{\vdash} $$ определяется как рефлексивное, транзитивное замыкание отношения $$\vdash $$.
Замечание 14.1.6. Если $$\lp x_1 , q_1 , a_1 , y_1 \rp \overstar{\vdash} \lp x_2 , q_2 , a_2 , y_2 \rp $$, то для любых $$k \in \mathbb{N} $$ и $$l \in \mathbb{N} $$ найдутся такие $$m \in \mathbb{N} $$ и $$n \in \mathbb{N} $$, что $$\lp b_0 ^k x_1 , q_1 , a_1 , y_1 b_0 ^l \rp \overstar{\vdash} \lp b_0 ^m x_2 , q_2 , a_2 , y_2 b_0 ^n \rp $$.
Замечание 14.1.7. Конфигурацию $$\lp b_0 ^m x , q , a , y b_0 ^n \rp $$ иногда изображают сокращенно $$x \underset{ q }{ a } y $$.
Замечание 14.1.8.
Машины Тьюринга можно изображать в виде диаграмм.
При этом каждое состояние обозначается кружком,
а переход - стрелкой.
Каждое начальное состояние распознается
по ведущей в него короткой стрелке.
Каждое заключительное состояние отмечается на диаграмме
двойным кружком.
Стрелка с пометкой a:ck,
ведущая из p в q,
показывает, что $$\lp \lp p , a \rp , \lp q , c , k \rp \rp $$
является переходом данной машины Тьюринга.
Обычно на диаграммах вместо чисел -1, 0, 1
(обозначающих движение влево, стояние на месте, движение вправо)
используются буквы L, N, R
соответственно.
Пример 14.1.9. Рассмотрим машину Тьюринга$$M \peq \lalg Q , \Sigma , \Gamma , b_0 , \Delta , I , F \ralg ,$$ где $$Q \peq \{ 0 , 1 , 2 , 3 \} $$, $$\Sigma \peq \{ a \} $$, $$\Gamma \peq \{ a , b \} $$, $$b_0 \peq b $$, $$I \peq \{ 0 \} $$, $$F \peq \{ 3 \} $$,$$\Delta \peq \{ \lp \lp 0 , b \rp \sqzcm \lp 1 , b , 1 \rp \rp \sqzcm \lp \lp 1 , a \rp \sqzcm \lp 2 , b , 1 \rp \rp \sqzcm \lp \lp 2 , a \rp \sqzcm \lp 1 , b , 1 \rp \rp \sqzcm \lp \lp 1 , b \rp \sqzcm \lp 3 , b , 0 \rp \rp \} .$$ $$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle \xymatrix { *=[o][F-]{0} \ar @`{+/l16mm/} [] ^{} \ar "1,2" ^{b:b\dr} *=[o][F-]{1} \ar "2,2" <0.6mm> ^{a:b\dr} \ar "1,3" ^{b:b\dn} *=[o][F=]{3} \\ % *=[o][F-]{2} \ar "1,2" <0.6mm> ^{a:b\dr} }$$ Можно проверить, что для любого $$k \in \mathbb{N} $$ выполняется следующее:$$\begin{align*} \underset{ 0 }{ b } a ^{k+1} \vdash \underset{ 1 }{ a } a ^k ,\\ \underset{ 1 }{ a } a ^{k+2} \overstar{\vdash} \underset{ 1 }{ a } a ^k ,\\ \underset{ 1 }{ a } a ^{2k+1} \overstar{\vdash} \underset{ 3 }{ b } . \end{align*}$$
Определение 14.1.10.
Машина Тьюринга$$\lalg Q , \Sigma , \Gamma , b_0 , \Delta , I , F \ralg$$
называется детерминированной,
если
множество I
содержит ровно один элемент
и
для каждой пары $$\lp p , a \rp \in ( Q \sminus F ) \times \Gamma $$
существует не более одной тройки $$\lp q , c , k \rp \in Q \times \Gamma \times \{ -1 , 0 , 1 \} $$
со свойством $$\lp \lp p , a \rp , \lp q , c , k \rp \rp \in \Delta $$.
Пример 14.1.11 Машина Тьюринга из примера 14.1.9 является детерминированной.
Определение 14.1.12.
Пусть f - частичная функция из $$\Sigma ^* $$
в $$\Sigma ^* $$.
Детерминированная машина Тьюринга$$M \peq \lalg Q , \Sigma , \Gamma , b_0 , \Delta , I , F \ralg$$
вычисляет
(computes)
функцию f
тогда и только тогда, когда
для каждого слова $$w \in \Sigma ^* $$
1) если f(w)
не определено,
то не существует таких $$p \in I $$, $$q \in F $$, $$a \in \Gamma $$, $$x \in \Gamma ^* $$, $$y \in \Gamma ^* $$,
что$$\lp \varepsilon , p , b_0 , w \rp
\overstar{\vdash} \lp x , q , a , y \rp ;$$
2) если f(w)=z,
то
для некоторых $$p \in I $$, $$q \in F $$, $$m \in \mathbb{N} $$
и $$n \in \mathbb{N} $$
выполнено условие$$\lp \varepsilon , p , b_0 , w \rp
\overstar{\vdash} \lp b_0 ^m , q , b_0 , z b_0 ^n \rp .$$
Определение 14.1.13. Частичная функция из $$\Sigma ^* $$ в $$\Sigma ^* $$ называется вычислимой, если существует детерминированная машина Тьюринга, вычисляющая эту функцию.
Пример 14.1.14. Машина Тьюринга из примера 14.1.9 вычисляет следующую частичную функцию:$$f( a ^n ) = \begin{cases} \varepsilon , \text{если число $ n $ четно,} \\ \text{не определено,} \text{если число $ n $ нечетно.} \end{cases}$$
Пример 14.1.15. Рассмотрим детерминированную машину Тьюринга$$\lalg Q , \Sigma , \Gamma , b_0 , \Delta , I , F \ralg ,$$ где$$\begin{align*} Q = \{ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 \} ,\\ \Sigma = \{ a \} ,\\ \Gamma = \{ a , b \} ,\\ b_0 = b ,\\ I = \{ 1 \} ,\\ F = \{ 7 \} ,\\ \Delta = \{ \lp \lp 1 , b \rp , \lp 2 , b , 1 \rp \rp ,\ \\ \hphantom{ {} = {} \{ } %\} \lp \lp 2 , b \rp , \lp 7 , b , 0 \rp \rp ,\ \lp \lp 2 , a \rp , \lp 3 , a , -1 \rp \rp ,\ \\ \hphantom{ {} = {} \{ } %\} \lp \lp 3 , b \rp , \lp 3 , a , 1 \rp \rp ,\ \lp \lp 3 , a \rp , \lp 4 , b , 1 \rp \rp ,\ \\ \hphantom{ {} = {} \{ } %\} \lp \lp 4 , b \rp , \lp 5 , b , -1 \rp \rp ,\ \lp \lp 4 , a \rp , \lp 8 , a , 0 \rp \rp ,\ \\ \hphantom{ {} = {} \{ } %\} \lp \lp 5 , b \rp , \lp 6 , b , -1 \rp \rp ,\ \\ \hphantom{ {} = {} \{ } %\} \lp \lp 6 , a \rp , \lp 6 , a , -1 \rp \rp ,\ \lp \lp 6 , b \rp , \lp 7 , b , 0 \rp \rp ,\ \\ \hphantom{ {} = {} \{ } %\} \lp \lp 8 , b \rp , \lp 8 , b , 1 \rp \rp ,\ \lp \lp 8 , a \rp , \lp 9 , a , 1 \rp \rp ,\ \\ \hphantom{ {} = {} \{ } %\} \lp \lp 9 , a \rp , \lp 9 , a , 1 \rp \rp ,\ \lp \lp 9 , b \rp , \lp 10 , b , -1 \rp \rp ,\ \\ \hphantom{ {} = {} \{ } %\} \lp \lp 10 , a \rp , \lp 11 , b , -1 \rp \rp ,\ \\ \hphantom{ {} = {} \{ } %\} \lp \lp 11 , b \rp , \lp 11 , b , 0 \rp \rp ,\ \lp \lp 11 , a \rp , \lp 12 , b , -1 \rp \rp ,\ \\ \hphantom{ {} = {} \{ } %\} \lp \lp 12 , a \rp , \lp 12 , a , -1 \rp \rp ,\ \lp \lp 12 , b \rp , \lp 13 , b , -1 \rp \rp ,\ \\ \hphantom{ {} = {} \{ } %\} \lp \lp 13 , b \rp ,\! \lp 13 , b , -1 \rp \rp ,\ \lp \lp 13 , a \rp ,\! \lp 14 , b , -1 \rp \rp ,\ \\ \hphantom{ {} = {} \{ } %\} \lp \lp 14 , a \rp ,\! \lp 8 , a , 1 \rp \rp ,\ \lp \lp 14 , b \rp ,\! \lp 3 , b , 1 \rp \rp \} . \end{align*}$$ $$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle \xymatrix { % *=[o][F=]{7} *=[o][F-]{6} \rloop{0,-1} ^{a:a\dl} \ar "1,2" _{b:b\dn} *=[o][F-]{5} \ar "1,3" _{b:b\dl} \\ % *=[o][F-]{1} \ar @`{+/l16mm/} [] ^{} \ar "2,3" ^{b:b\dr} *=[o][F-]{2} \ar "1,2" ^*!/u1.5mm/{b:b\dn} \ar "3,2" ^*!/u2mm/{a:a\dl} \\ % *=[o][F-]{3} \rloop{0,1} ^{b:a\dr} \ar "3,4" ^{a:b\dr} *=[o][F-]{4} \ar "1,4" _{b:b\dl} \ar "3,5" ^{a:a\dn} *=[o][F-]{8} \rloop{0,1} ^{b:b\dr} \ar "3,6" ^{a:a\dr} *=[o][F-]{9} \rloop{0,1} ^{a:a\dr} \ar "4,5" ^{b:b\dl} \\ *=[o][F-]{14} \ar "3,5" <-0.2mm> ^-(.3){a:a\dr} \ar "3,2" ^{b:b\dr} *=[o][F-]{13} \rloop{0,-1} ^{b:b\dl} \ar "4,1" ^{a:b\dl} *=[o][F-]{12} \rloop{0,-1} ^{a:a\dl} \ar "4,2" ^{b:b\dl} *=[o][F-]{11} \rloop{0,-1} ^{b:b\dn} \ar "4,3" ^{a:b\dl} *=[o][F-]{10} \ar "4,4" ^{a:b\dl} }$$ Можно проверить, что для любых $$i \in \mathbb{N} $$, $$j \in \mathbb{N} $$ и $$k \in \mathbb{N} $$ выполняется следующее:$$\begin{align*} \underset{ 1 }{ b } a ^{k+2} \overstar{\vdash} a b \underset{ 8 }{ a } a ^k ,\\ a b ^{j+1} \underset{ 8 }{ a } a ^2 \overstar{\vdash} \underset{ 7 }{ b } a ^{j+2} ,\\ a b ^{j+1} \underset{ 8 }{ a } a ^{k+3} \overstar{\vdash} a ^{j+2} b \underset{ 8 }{ a } a ^k ,\\ a ^{i+2} b ^{j+1} \underset{ 8 }{ a } a ^{k+2} \overstar{\vdash} a ^{i+1} b ^{j+2} \underset{ 8 }{ a } a ^k ,\\ a b ^{j+1} \underset{ 8 }{ a } a ^{k+2j+5} \overstar{\vdash} a b ^{j+2} \underset{ 8 }{ a } a ^k . \end{align*}$$ Следовательно,$$\begin{align*} \underset{ 1 }{ b } a ^{i+(j+2)^2} \squeeze{\overstar{\vdash}} a b ^{j+1} \underset{ 8 }{ a } a ^{i+2} ,\\ \underset{ 1 }{ b } a ^{(k+2)^2} \overstar{\vdash} \underset{ 7 }{ b } a ^{k+2} . \end{align*}$$ Рассматриваемая машина Тьюринга вычисляет следующую частичную функцию:$$f( a ^n ) = \begin{cases} a^{\sqrt{n}} , \text{если $ \sqrt{n} \in \mathbb{N} $,} \\ \text{не определено,} \text{если $ \sqrt{n} \notin \mathbb{N} $.} \end{cases}$$
Замечание 14.1.16. Тезисом Черча-Тьюринга (а иногда просто тезисом Черча ) называется следующее неформальное утверждение: для каждой вычислимой в интуитивном смысле частичной функции из $$\Sigma ^* $$ в $$\Sigma ^* $$ существует машина Тьюринга, которая эту функцию вычисляет.
Упражнение 14.1.17.
Найти детерминированную машину Тьюринга
с входным алфавитом {a},
вычисляющую функцию f,
заданную соотношением
f(an) = an+1.
Упражнение 14.1.18.
Найти детерминированную машину Тьюринга
с входным алфавитом {a},
вычисляющую функцию f,
заданную соотношением$$f(a^n) = \varepsilon .$$
Определение 14.1.19.
Зафиксируем два различных символа a и b
и положим $$\Sigma = \{a,b\} $$.
Пусть k -
положительное целое число
и f -
частичная функция из $$\mathbb{N}^k $$
в $$\mathbb{N} $$.
Детерминированная машина Тьюринга$$M \peq \lalg Q , \Sigma , \Gamma , b , \Delta , I , F \ralg$$
вычисляет
функцию f
тогда и только тогда, когда
для любых натуральных чисел $$n_1 , \ldots , n_k $$
выполняются следующие условия:
1) если $$f ( n_1 , \ldots , n_k ) $$ не определено, то не существует таких $$p \in I $$, $$q \in F $$, $$a \in \Gamma $$, $$x \in \Gamma ^* $$, $$y \in \Gamma ^* $$, что$$\lp \varepsilon , p , b , a^{n_1} b a^{n_2} b \ldots b a^{n_k} \rp \overstar{\vdash} \lp x , q , a , y \rp ;$$
2) если $$f ( n_1 , \ldots , n_k ) = l $$, то для некоторых $$p \in I $$, $$q \in F $$, $$m \in \mathbb{N} $$ и $$n \in \mathbb{N} $$ выполнено условие$$\lp \varepsilon , p , b , a^{n_1} b a^{n_2} b \ldots b a^{n_k} \rp \overstar{\vdash} \lp b ^m , q , b_0 , a^l b ^n \rp .$$
Упражнение 14.1.20. Рассмотрим детерминированную машину Тьюринга, изображенную на рисунке.$$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle \xymatrix { *=[o][F-]{1} \ar @`{+/l16mm/} [] ^{} \ar "1,2" ^{b:b\dr} *=[o][F-]{2} \ar "1,3" ^{a:b\dr} \ar "2,3" _{b:b\dn} *=[o][F-]{3} \ar "1,4" ^{a:b\dr} \ar "2,3" ^{b:b\dn} *=[o][F-]{4} \ar "1,5" ^{a:b\dr} \ar "2,3" ^{b:b\dn} *=[o][F-]{5} \rloop{0,1} ^{a:b\dr} \ar "2,5" ^{b:b\dn} \\ % *=[o][F=]{6} *=[o][F=]{7} }$$ Какую функцию из $$\mathbb{N} $$ в $$\mathbb{N} $$ она вычисляет?
Упражнение 14.1.21. Рассмотрим детерминированную машину Тьюринга, изображенную на рисунке.$$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle \xymatrix { % *=[o][F-]{6} \rloop{0,1} ^{b:b\dr} \ar "1,3" ^{a:a\dr} *=[o][F-]{7} \rloop{0,1} ^{a:a\dr} \ar "2,3" ^{b:a\dl} *=[o][F-]{1} \ar @`{+/l16mm/} [] ^{} \ar "1,6" ^{b:a\dr} *=[o][F-]{2} \rloop{0,1} ^{a:a\dr} \ar "1,7" ^{b:b\dr} *=[o][F-]{3} \rloop{0,1} ^{a:b\dr} \ar @/^4mm/ "3,2" ^{b:a\dl} \\ % *=[o][F-]{8} \rloop{0,-1} ^{a:a\dl} \ar "3,2" _{b:b\dl} \\ *=[o][F-]{5} \ar "1,2" ^{a:a\dr} \ar "4,2" _{b:b\dr} *=[o][F-]{4} \rloop{0,-1} ^{b:b\dl} \ar "3,1" _{a:b\dl} *=[o][F-]{10} \ar "4,7" ^{b:a\dr} \\ % *=[o][F-]{9} \rloop{0,-1} ^{a:b\dl} \ar "3,5" ^{b:b\dr} *=[o][F-]{15} \rloop{0,-1} ^{a:a\dl} \ar "4,5" ^{b:a\dr} *=[o][F-]{16} \rloop{0,1} ^{a:a\dr} \ar "4,7" ^{b:b\dr} *=[o][F-]{11} \rloop{0,1} ^{b:b\dr} \ar "5,6" ^{a:a\dl} \\ % *=[o][F-]{14} \rloop{0,-1} ^{b:b\dl} \ar "4,3" ^(0.3){a:a\dl} *=[o][F-]{13} \ar "5,4" ^{b:b\dl} \ar "6,4" ^{a:b\dl} *=[o][F-]{12} \ar "5,5" ^{b:a\dl} \ar "6,7" ^(0.3){a:b\dr} \\ % *=[o][F-]{17} \ar "4,2" ^{a:b\dl} \ar "6,7" ^{b:b\dr} *=[o][F-]{18} \rloop{0,1} ^{b:b\dr} \ar "7,7" ^{a:b\dn} \\ % *=[o][F=]{19} }$$ Какую функцию из $$\mathbb{N} \times \mathbb{N} $$ в $$\mathbb{N} $$ она вычисляет?
Определение 14.2.1.
Говорят, что детерминированная машина Тьюринга$$\lalg Q , \Sigma , \Gamma , b_0 , \Delta ,
\{ \qinitial \} , \{ \qaccept , \qreject \} \ralg$$
с выделенным состоянием qa разрешает
(decides) язык $$L \subseteq \Sigma ^* $$,
если
1) для каждого слова $$w \in L $$ найдутся такие $$m \in \mathbb{N} $$ и $$n \in \mathbb{N} $$, что $$\lp \varepsilon , \qinitial , b_0 , w \rp \overstar{\vdash} \lp b_0 ^m , \qaccept , b_0 , b_0 ^n \rp $$ ;
2) для каждого слова $$w \in \Sigma ^* \sminus L $$
найдутся такие $$m \in \mathbb{N} $$
и $$n \in \mathbb{N} $$,
что $$\lp \varepsilon , \qinitial , b_0 , w \rp \overstar{\vdash} \lp b_0 ^m , \qreject , b_0 , b_0 ^n \rp $$.
Состояние qa
называется допускающим
( принимающим, accept state),
состояние qr
называется отвергающим
( непринимающим, (
Пример 14.2.2. Рассмотрим детерминированную машину Тьюринга$$M \peq \lalg Q , \Sigma , \Gamma , b_0 , \Delta , \{ \qinitial \} , \{ \qaccept , \qreject \} \ralg ,$$ где $$Q = \{ 0 , 1 , 2 , 3 , 4 , 5 \} $$, $$\Sigma = \{ a \} $$, $$\Gamma = \{ a , b \} $$, $$b_0 = b $$, $$\qinitial = 0 $$, $$\qaccept = 4 $$, $$\qreject = 5 $$ и$$\begin{align*} {} \Delta = \{ \lp \lp 0 , b \rp , \lp 1 , b , 1 \rp \rp ,\ \\ \hphantom{ {} = {} \{ } %\} \lp \lp 1 , a \rp , \lp 2 , b , 1 \rp \rp ,\ \lp \lp 2 , a \rp , \lp 3 , b , 1 \rp \rp ,\ \lp \lp 3 , a \rp , \lp 1 , b , 1 \rp \rp ,\ \\ \hphantom{ {} = {} \{ } %\} \lp \lp 1 , b \rp , \lp 4 , b , 0 \rp \rp ,\ \lp \lp 2 , b \rp , \lp 5 , b , 0 \rp \rp ,\ \lp \lp 3 , b \rp , \lp 5 , b , 0 \rp \rp \} . \end{align*}$$ $$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle \xymatrix { *=[o][F-]{0} \ar @`{+/l16mm/} [] ^{} \ar "1,2" ^{b:b\dr} *=[o][F-]{1} \ar "1,3" ^{a:b\dr} \ar "2,2" ^{b:b\dn} *=[o][F-]{2} \ar "1,4" ^{a:b\dr} \ar "2,4" _{b:b\dn} *=[o][F-]{3} \ar `ul^l{+/u7mm/}`l^dl{[0,-2]}_{a:b\dr} "1,2" \ar "2,4" ^{b:b\dn} \\ % *=[o][F=]{4} *=[o][F=]{5} }$$ Эта машина Тьюринга разрешает язык $$\{ a^{3n} \mid n \in \mathbb{N} \} $$.
Определение 14.2.3.
Язык L
над алфавитом $$\Sigma $$
называется разрешимым
или рекурсивным (decidable, recursive),
если
существует детерминированная машина Тьюринга$$\lalg Q , \Sigma , \Gamma , b_0 , \Delta ,
\{ \qinitial \} , \{ \qaccept , \qreject \} \ralg$$
(с выделенным состоянием qa ),
которая разрешает язык L.
Определение 14.2.4. Говорят, что машина Тьюринга$$M \peq \lalg Q , \Sigma , \Gamma , b_0 , \Delta , \{ \qinitial \} , \{ \qaccept \} \ralg$$ допускает ( принимает, accepts) слово $$w \in \Sigma ^* $$, если для некоторых $$m \in \mathbb{N} $$ и $$n \in \mathbb{N} $$ $$\lp \varepsilon , \qinitial , b_0 , w \rp \overstar{\vdash} \lp b_0 ^m , \qaccept , b_0 , b_0 ^n \rp $$.
Определение 14.2.5.
Язык, допускаемый
машиной Тьюринга M, -
это язык, состоящий из всех допускаемых данной машиной Тьюринга слов.
Определение 14.2.6. Язык называется перечислимым ( рекурсивно перечислимым, полуразрешимым, recursively enumerable), если существует детерминированная машина Тьюринга, допускающая этот язык.
Замечание 14.2.7. В определении 14.2.6 можно отбросить требование детерминированности машины Тьюринга.
Теорема 14.2.8. Каждый разрешимый язык является перечислимым.
Доказательство.
Пусть дана машина Тьюринга$$M \peq \lalg Q , \Sigma , \Gamma , b_0 , \Delta ,
\{ \qinitial \} , \{ \qaccept , \qreject \} \ralg$$
с выделенным состоянием qa,
которая разрешает язык $$L \subseteq \Sigma ^* $$.
Тогда машина Тьюринга$$M' \peq \lalg Q , \Sigma , \Gamma , b_0 , \Delta ,
\{ \qinitial \} , \{ \qaccept \} \ralg$$
допускает язык L.
Пример 14.2.9. Если в машине Тьюринга из примера 14.1.15 заменить переход $$\lp \lp 6 , a \rp , \lp 6 , a , -1 \rp \rp $$ на $$\lp \lp 6 , a \rp , \lp 6 , b , -1 \rp \rp $$, то получится машина Тьюринга, допускающая язык $$\{ a^{n^2} \mid n \in \mathbb{N} \} $$. Следовательно, этот язык является перечислимым. Можно доказать, что он даже является разрешимым.
Теорема 14.2.10. Существует такая машина Тьюринга над однобуквенным алфавитом $$\Sigma = \{ a \} $$, что язык, допускаемый этой машиной Тьюринга, неразрешим.
Доказательство. Доказательство существования перечислимого неразрешимого множества можно найти, например, в [31, 9.2].
Упражнение 14.2.11.
Найти детерминированную машину Тьюринга
с входным алфавитом {a},
разрешающую язык $$\{ a^{n} \mid n \leq 2 \} $$.
Упражнение 14.2.12.
Найти детерминированную машину Тьюринга
с входным алфавитом {a},
допускающую язык $$\{ a^{3n+2} \mid n \geq 0 \} $$
Определение 14.3.1. Массовой задачей
(problem)
называется
бесконечная серия "однотипных" индивидуальных задач
(instance),
каждая из которых имеет определенный ответ.
С каждой массовой задачей связана некоторая фиксированная схема кодирования
(
Определение 14.3.2. Задачей распознавания (decision problem) называется массовая задача, в которой ответами индивидуальных задач могут быть только "да" и "нет" (то есть существует только два возможных ответа).
Пример 14.3.3.
Зафиксируем некоторый алфавит $$\Sigma $$.
Рассмотрим следующие однотипные индивидуальные задачи:
даны два слова $$x \in \Sigma ^* $$
и $$y \in \Sigma ^* $$,
необходимо выяснить, является ли
слово x
подсловом слова y.
Пусть # -
новый символ, не принадлежащий алфавиту $$\Sigma $$.
Кодом индивидуальной задачи про конкретные
слова x и y
будем считать слово x#y
в алфавите $$\Sigma \cup \{ \# \} $$.
Эта массовая задача является задачей распознавания.
Определение 14.3.4. Алгоритмическая проблема -
проблема, в которой требуется найти алгоритм для решения
массовой задачи.
Если такой алгоритм существует, то данная проблема называется алгоритмически разрешимой
или просто разрешимой (decidable,
Замечание 14.3.5.
Алгоритмическая проблема,
относящаяся к некоторой задаче распознавания,
алгоритмически разрешима
тогда и только тогда, когда
Пример 14.3.6. Рассмотрим массовую задачу из примера 14.3.3. Соответствующая алгоритмическая проблема разрешима, так как разрешим язык $$\{ x \# u x v \mid x \in \Sigma ^* ,\ u \in \Sigma ^* \commaand v \in \Sigma ^* \} $$.
Пример 14.3.7. Зафиксируем некоторый алфавит $$\Sigma $$. Рассмотрим следующие однотипные индивидуальные задачи: дана порождающая грамматика$$G = \lalg \{ A_1 , \ldots , A_n \} , \Sigma , P , A_1 \ralg ,$$ необходимо выяснить, является ли эта грамматика праволинейной.
Для полной строгости необходимо договориться, как
кодировать грамматику G
в виде слова.
Например, можно использовать алфавит $$\Sigma \cup \{ \heartsuit , \spadesuit , 0 , 1 \} $$,
где $$\heartsuit $, $ \spadesuit $, $ 0 $, $ 1 $$ -
дополнительные символы, не принадлежащие множеству $$\Sigma $$.
Вспомогательный символ Ai
заменим на слово, состоящее из
символа $$\heartsuit $$
и кода числа i
в двоичной системе счисления.
В каждом правиле $$\alpha \tto \beta $$
добавим символ $$\spadesuit $$
на месте $$\to $$
и после слова $$\beta $$.
Кодом грамматики G
будем считать результат конкатенации кодов всех правил
из множества P.
Например, грамматика$$\begin{align*}
A_1 \; {\to} \; a , \\
A_1 \; {\to} \; A_2 A_1 , \\
A_2 \; {\to} \; a A_3 , \\
A_3 \; {\to} \; \varepsilon , \\
A_3 \; {\to} \; b A_1
\end{align*}$$
(над алфавитом $$\Sigma = \{ a , b \} $$ )
кодируется словом$$\heartsuit 1 \spadesuit
a \spadesuit
\heartsuit 1 \spadesuit
\heartsuit 1 0 \heartsuit 1 \spadesuit
\heartsuit 1 0 \spadesuit
a \heartsuit 1 1 \spadesuit
\heartsuit 1 1 \spadesuit
\spadesuit
\heartsuit 1 1 \spadesuit
b \heartsuit 1 \spadesuit .$$
Легко понять, что соответствующая алгоритмическая проблема (проблема проверки праволинейности) разрешима.
Упражнение 14.3.8.
Разрешима ли алгоритмическая проблема распознавания
четности длины слова над алфавитом {a,b}?
Теорема 14.4.1. Класс языков, порождаемых грамматиками типа 0, совпадает с классом перечислимых языков.
Доказательство можно найти, например, в [СерГал с. 24-26].
Упражнение 14.4.2.
Выводимо ли слово aab
в грамматике$$\begin{align*}
S \; {\to} \; S b , T a \; {\to} \; a a T , \\
S \; {\to} \; S T , T b \; {\to} \; a b , \\
S \; {\to} \; S U , U a a a \; {\to} \; a a U , \\
S \; {\to} \; \varepsilon , U a b \; {\to} \; b ?
\end{align*}$$
Упражнение 14.4.3.
Выводимо ли слово aaaaaaaab
в грамматике$$\begin{align*}
S \; {\to} \; S b , T a \; {\to} \; a a T , \\
S \; {\to} \; S T , T b \; {\to} \; a b , \\
S \; {\to} \; S U , U a a a \; {\to} \; a a U , \\
S \; {\to} \; \varepsilon , U a b \; {\to} \; b ?
\end{align*}$$
Замечание 14.4.4.
Неизвестно,
порождает ли грамматика$$\begin{align*}
R \; {\to} \; Ra , Ta \; {\to} \; aaT , \\
R \; {\to} \; S , Tb \; {\to} \; ab , \\
S \; {\to} \; Sb , Uaaa \; {\to} \; aaU , \\
S \; {\to} \; ST , Uab \; {\to} \; b \\
S \; {\to} \; SU , \\
S \; {\to} \; \varepsilon ,
\end{align*}$$
все слова в алфавите {a,b}.
Упражнение 14.4.5.
Пусть $$\Sigma = \{ a , b , c , d , e \} $$.
Рассмотрим грамматику$$\begin{align*}
R \; {\to} \; ccdcdcddccddcdccca , ce \; {\to} \; eca , \\
ac \; {\to} \; ca , eca \; {\to} \; ce , \\
ca \; {\to} \; ac , de \; {\to} \; edb , \\
bc \; {\to} \; cb , edb \; {\to} \; de , \\
cb \; {\to} \; bc , cca \; {\to} \; ccae , \\
ad \; {\to} \; da , ccae \; {\to} \; cca . \\
da \; {\to} \; ad , \\
bd \; {\to} \; db , \\
db \; {\to} \; bd ,
\end{align*}$$
Выводимо ли в ней слово ccdcdcddccddcdcccabba?
Упражнение 14.4.6. Является ли разрешимым язык, порождаемый грамматикой$$\begin{align*} S \; {\to} \; c S , ac \; {\to} \; ca , cdc \; {\to} \; cdc R , \\ S \; {\to} \; d S , ca \; {\to} \; ac , R cca \; {\to} \; cc R , \\ S \; {\to} \; aa , bc \; {\to} \; cb , R ddb \; {\to} \; dd R , \\ cb \; {\to} \; bc , R cdd \; {\to} \; cdd T , \\ ad \; {\to} \; da , T cc \; {\to} \; cca T , \\ da \; {\to} \; ad , T dd \; {\to} \; ddb T , \\ bd \; {\to} \; db , T cdc \; {\to} \; cdc ? \\ db \; {\to} \; bd , \end{align*}$$
Определение 14.4.7. Порождающая грамматика в нормальной форме - это порождающая грамматика, в которой каждое правило имеет вид $$A \to a $$, $$A \to B C $$ или $$A B \to \varepsilon $$, где $$A \in N $$, $$B \in N $$, $$C \in N $$, $$a \in \Sigma $$.
Теорема 14.4.8. Каждая порождающая грамматика эквивалентна некоторой порождающей грамматике в нормальной форме.
Упражнение 14.4.9.
Существует ли такая порождающая грамматика G,
что язык $$L(G) \sminus \{ \varepsilon \} $$
не порождается ни одной грамматикой типа 0?
Определение 14.5.1. Постовской системой соответствия
над алфавитом $$\Sigma $$
называется упорядоченная
пара конечных последовательностей $$(( x_1 , \ldots , x_n ) , ( y_1 , \ldots , y_n )) $$,
где $$x_i \in \Sigma ^* $$
и $$y_i \in \Sigma ^* $$
для всех i.
Замечание 14.5.2. Систему $$(( x_1 , \ldots , x_n ) , ( y_1 , \ldots , y_n )) $$ иногда изображают в виде$$\domino{x_1}{y_1} , \ldots , \domino{x_n}{y_n} .$$
Определение 14.5.3. Решением (match)
постовской системы соответствия ((x1,...,xn),(y1,...,yn))
называется непустая последовательность индексов $$(i_1 , \ldots , i_k) $$,
удовлетворяющая условию$$x_{i_1} \ldots x_{i_k} = y_{i_1} \ldots y_{i_k} ,$$
где $$1 \leq i_j \leq n $$
для каждого j.
Пример 14.5.4.
Пусть $$\Sigma = \{ a , b , c \} $$.
Рассмотрим постовскую систему соответствия$$\domino{ a a b }{ a } ,
\domino{ a }{ a a } ,
\domino{ c a a }{ b c } .$$
Последовательность (2,1,3,2,2)
является решением этой системы,
так как$$a \cdot aab \cdot caa \cdot a \cdot a =
aa \cdot a \cdot bc \cdot aa \cdot aa .$$
Упражнение 14.5.5. Пусть $$\Sigma = \{ a , b , c , 0 , 1 , \diamondsuit , \heartsuit, \spadesuit \} $$. Существует ли решение у постовской системы соответствия$$\begin{gathered*} \domino{ a \spadesuit } { a \spadesuit a b a \heartsuit 1 a c a \spadesuit a } , \domino{ a b }{ b a } , \domino{ a c }{ c a } , \domino{ a \spadesuit }{ \spadesuit a } , \domino{ a \spadesuit }{ b a \spadesuit a } , \domino{ a \spadesuit }{ \spadesuit a b a } , \\ \!\domino{ a \heartsuit 1 a b }{ \diamondsuit a }\! , \!\domino{ a \heartsuit 1 a c }{ c a \heartsuit 1 0 a }\! , \!\domino{ a b a \heartsuit 1 0 a b }{ \heartsuit 1 0 a b a c a }\! , \!\domino{ a c a \heartsuit 1 0 a b }{ \heartsuit 1 0 a c a c a }\! , \!\domino{ a \heartsuit 1 0 a c }{ c a \heartsuit 1 1 a }\! , \!\domino{ a \heartsuit 1 1 a c }{ c a \heartsuit 1 a }\! , \\ \domino{ a \diamondsuit a b }{ \diamondsuit a } , \domino{ a \diamondsuit a c }{ \diamondsuit a } , \domino{ a b a \diamondsuit }{ \diamondsuit a } , \domino{ a c a \diamondsuit }{ \diamondsuit a } , \domino{ a \diamondsuit a \spadesuit a \spadesuit }{ \spadesuit } ? \end{gathered*}$$
Определение 14.5.6. Проблемой соответствий Поста (Post correspondence problem) называется проблема нахождения алгоритма, выясняющего для каждой постовской системы соответствия, существует ли решение этой системы.
Теорема 14.5.7. Пусть $$| \Sigma | \geq 2 $$. Тогда не существует алгоритма, позволяющего по произвольной постовской системе соответствия над алфавитом $$\Sigma $$ узнать, имеет ли она решение. ( Другими словами, проблема соответствий Поста неразрешима.)
Доказательство можно найти в [ХопМот, 9.4].
Упражнение 14.5.8. Существует ли решение у постовской системы соответствия $$\domino{ab}{abab} , \domino{b}{a} , \domino{aba}{b} , \domino{aa}{a} $$?
Упражнение 14.5.9. Существует ли решение у постовской системы соответствия $$\domino{b}{ca}, \domino{a}{ab}, \domino{ca}{a}, \domino{abc}{c} $$?
Упражнение 14.5.10. Существует ли решение у постовской системы соответствия $$\domino{a}{ab}, \domino{ca}{cc}, \domino{bcc}{ccca}, \domino{b}{ab} $$?
Упражнение 14.5.11. Существует ли решение у постовской системы соответствия $$\domino{ab}{aba}, \domino{b}{a}, \domino{aba}{b}, \domino{bbab}{abb} $$?
Упражнение 14.5.12. Существует ли решение у постовской системы соответствия $$\domino{ab}{b}, \domino{b}{bba}, \domino{ba}{b}, \domino{b}{bab}, \domino{b}{abb} $$?
Упражнение 14.5.13. Существует ли решение у постовской системы соответствия $$\domino{ab}{b}, \domino{b}{bba}, \domino{ba}{b}, \domino{aba}{aba} $$?
Упражнение 14.5.14. Существует ли решение у постовской системы соответствия $$\domino{a}{aaa}, \domino{\varepsilon}{aaaaa}, \domino{aaaaa}{aa} $$?
Упражнение 14.5.15. Существует ли постовская система соответствия, имеющая ровно одно решение?
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.