В.Н. Пильщиков, В.Г. Абрамов, А.А. Вылиток, И.В. Горячая - Машина Тьюринга и алгоритмы Маркова. Решение задач (1000390), страница 9
Текст из файла (страница 9)
начав работать над своейзаписью как входным словом, он остановится:1a →#;# a ;→#Алгоритм же H2 несамоприменим, т.к. он зацикливается на своей записи:#a→#;# a ;→#→2#→#;# a ;→#4a→b;b→bb→5b→b;b→bb→5bb→b;b→bb→5bbb→b;b→bb→…Отметим, что если применимость зависит как от алгоритма, так и от слова,то самоприменимость зависит только от алгоритма, от того, применим ли этот38алгоритм к конкретному слову – к своей собственной записи, котораяоднозначно определяется данным алгоритмом.Пример 3Построить НАМ, который несамоприменим, но применим к любому слову валфавите {a,b}.РешениеПоскольку искомый НАМ применим ко всем словам, составленным изсимволов a и b, то зацикливаться он может лишь на словах, содержащих какойто дополнительный символ, скажем *.
Следовательно, чтобы НАМ оказалсянесамоприменимым (зацикливался на своей записи), символ * должен входить взапись алгоритма (в одну из его формул) и на этом символе НАМ долженциклиться. Можно придумать много таких алгоритмов, но простейшим из нихявляется следующий:{ *→*Пример 4Известно, что проблема самоприменимости алгоритмически неразрешима,т.е. не существует единого способа (алгоритма), который позволял быопределять для любого алгоритма, самоприменим он или нет. Однако в частныхслучаях (для некоторых классов алгоритмов) эта проблема может оказаться иразрешимой.
Например, проблема самоприменимости для НАМ, содержащихтолько одну формулу подстановки, разрешима. Требуется доказать этоутверждение.ДоказательствоПусть НАМ имеет вид { α ⏐→ β или { α → β. Тогда можно использоватьследующий метод проверки самоприменимости: если единственная формулаалгоритма заключительная или если это обычная формула, левая часть (α)которой не входит в правую часть (β), то такой НАМ самоприменим, иначе жеон несамоприменим.Действительно, какой бы ни была единственная формула –заключительной или обычной, на первом шаге применения НАМ к его записи (кслову α⏐→β или α→ β) часть α в этой записи будет заменена на β, в результатечего получится слово β⏐→β или β→β.
Если формула заключительная, то на этомНАМ и остановится, а это значит, что он самоприменим. Если же формулаобычная и α не входит в β, то формула неприменима к получившемуся слову иработа НАМ прекращается, поэтому и в данном случае алгоритм самоприменим. Но если формула обычная и α входит в β, то в получившемся слове β→βбудет присутствовать α, поэтому наша формула снова применяется, причем в39новом слове по-прежнему окажется α.
Получаем бесконечный процесс подстановок, а это и значит, что НАМ несамоприменим.3.3 Эквивалентность алгоритмовЭквивалентными называются алгоритмы, которые предлагают разныеспособы решения одной и той же задачи. Это значит, что на одинаковых входных словах они выдают одинаковые результаты (выходные слова). При этом,правда, надо учитывать и случай зацикливания: если один алгоритм зацикливается на каких-то входных словах, т.е. не даёт решение задачи, то и эквивалентный ему алгоритм также не должен давать решения на этих исходныхданных.Точное определение эквивалентности алгоритмов следующее: алгоритмыH1 и H2 эквивалентны относительно алфавита A, если области применимости H1 и H2 относительно алфавита A совпадают и для любого слова P изэтой области выполняется равенство H1(P) = H2(P).Отметим, что в этом определении важен тот алфавит, относительно которого устанавливается эквивалентность. Дело в том, что одни и те же алгоритмымогут быть эквивалентными относительно одного алфавита и не эквивалентными относительно другого алфавита.
Например, алгоритмы⎧aaaH2 : ⎨⎩ b →bэквивалентны относительно алфавита {a} и не эквивалентны относительноалфавита {a,b}: слова в алфавите {a} они не меняют, но если в входное слововходят только символы b, то H1 остановится, а H2 зациклится.H1 :{a a aПример 5Определить, эквивалентны ли следующие пары НАМ относительно алфавита {a,b}:1) H1 :{a a b⎧ a→b2) H3 : ⎨⎩b→a3) H5 :{ aa → a⎧ *b → b *⎪H2 : ⎨ * a a b⎪⎩→*⎧ a → aaH4 : ⎨⎩ b → bb⎧ * aa⎪ *bH6 : ⎨*⎪⎩→ a*→ b*a→*РешениеПри проверке алгоритмов на эквивалентность надо прежде всегоустановить, совпадают ли области их применимости.В случае алгоритмов Н1 и Н2, которые первое вхождение символа aзаменяют на b, это условие не выполняется: Н1 применим ко всем словам из40символов a и b, а Н2 зацикливается на словах, не содержащих a. Значит,алгоритмы Н1 и Н2 не эквивалентны.Если же области применимости совпадают, тогда надо показать, что наодних и тех же словах из данной области эти алгоритмы выдают одинаковыерезультаты.У пары алгоритмов Н3 и Н4 одна и та же область применимости – онасостоит только из одного пустого слова.
На непустых же словах эти алгоритмызацикливаются, причём зацикливаются по-разному: Н3 постоянно меняет a на bи b на a, тогда как Н4 всё время добавляет новый символ a или b. Однако такоеразличное поведение при зацикливании не играет никакой роли при определении эквивалентности алгоритмов. Важно лишь, чтобы в случае остановаалгоритмы выдавали одинаковые выходные слова. А для пары Н3 и Н4 этоусловие выполняется: на единственном слове (пустом), к которому ониприменимы, они выдают один и тот же ответ – пустое слово. Значит, алгоритмыН3 и Н4 эквивалентны.Теперь рассмотрим пару алгоритмов Н5 и Н6. У них одна и та же областьприменимости – это множество всех слов в алфавите {a,b}. Однако второеусловие эквивалентности (одинаковые результаты при одинаковых исходныхданных) не выполняется.
Чтобы доказать это, достаточно привести лишь однослово, на котором алгоритмы выдают разные ответы. Таким словом может быть,например, слово aaaa:H5: aaaa → aaa → aa → aH6: aaaa → *aaaa → a*aa → aa* a aaИтак, алгоритмы Н5 и Н6 не эквивалентны.3.4 Композиция алгоритмовКак известно, к результату одной функции можно применить другуюфункцию, например: sin(ctg x).
Точно так же выходное слово одного алгоритмаН1 можно подать на вход другому алгоритму Н2. Такое последовательное выполнение сначала алгоритма Н1, а затем алгоритма Н2 называется композициейэтих алгоритмов. При этом, правда, надо учитывать, что любой из этих алгоритмов может зацикливаться, тогда должна зацикливаться и их композиция.Эти соображения приводят к следующему определению:Композицией алгоритмов H1 и H2 относительно алфавита A называетсятакой алгоритм H (обозначается Н1°Н2 или H2(H1)), что для любого слова P валфавите A выполняются следующие условия:1) если Н1 неприменим к Р, то и Н неприменим к Р;2) если Н1 применим к Р, но Н2 неприменим к слову Н1(Р), то и Н неприменим к Р;3) если Н1 применим к Р и Н2 применим к слову Н1(Р), то Н применим к Р,причём выполняется равенство Н(Р)=Н2(Н1(Р)).41Доказана следующая теорема: для любых нормальных алгоритмов Н1 и Н2существует нормальный алгоритм Н, который является (относительно соответствующего алфавита) композицией Н1 и Н2.
(Аналогичная теорема верна и длямашины Тьюринга.)Пример 6Построить нормальный алгоритм Н, являющийся композицией указанныхнормальных алгоритмов Н1 и Н2 (Н=Н2(Н1))) относительно алфавита {a,b}:⎧ *a⎪ *bH1 : ⎨*⎪⎩→*→ b*a→*H2 :{ b→aРешениеПрежде всего отметим, что в общем случае нельзя строить композицию Нпростым выписыванием друг за другом формул подстановки из алгоритмов Н1и Н2. Например, если сначала выписать формулы из Н1, а затем из Н2, тополучим алгоритм Н12, а если сначала выписать формулы из Н2, а затем из Н1,то получим алгоритм Н21:⎧ *a → *⎧b → a⎪ *b → b *⎪* a → *⎪⎪H12 : ⎨ * aH21 : ⎨ * b → b *⎪⎪* a→*⎪b →a⎪→*⎩⎩Так вот, ни Н12, ни Н21 не является композицией алгоритмов Н1 и Н2.Например, для входного слова abb имеем:H12: abb → *abb → *bb → b*b → bb* a bbH21: abb → aab → aaa → *aaa → *aa → *a → * aтогда как H2(H1(abb))=H2(bb)=aa.Отметим, что существует на самом деле способ построения списка формулдля композиции Н по спискам формул из Н1 и Н2 (наличие этого способа идоказывает указанную выше теорему).
Однако этот способ достаточногромоздкий, поэтому для несложных НАМ лучше использовать другой подход:прежде всего следует понять, какую задачу решает каждый из алгоритмов Н1 иН2, затем надо последовательность этих задач объединить в общую задачу и,наконец, построить алгоритм для решения этой общей задачи. Такой алгоритм ибудет композицией исходных алгоритмов.В нашем примере алгоритм Н1 удаляет из входного слова все символы a,алгоритм же Н2 заменяет все b на a. Значит, последовательное применениесначала Н1, а затем Н2 приводит к тому, что из входного слова удаляются всесимволы a, после чего оставшиеся символы b заменяются на a (без последующего удаления их).
НАМ, решающий такую задачу, может быть, например,следующим:42⎧ *a → *⎪ *b → a *H: ⎨* a⎪→*⎩Это и есть композиция заданных алгоритмов Н1 и Н2.3.5 Задачи для самостоятельного решения3.1 Из указанного НАМ вычеркнуть ровно одну формулу подстановки так,чтобы получился алгоритм, применимый ко всем словам в алфавите {a,b}:⎧ a →b⎪⎨ ba → aba⎪⎩ b → a3.2 Определить область применимости указанного НАМ относительноалфавита {a,b,c}:⎧ ba → ab⎪ ca → ac⎪д) ⎨ cb → bc⎪ abc a⎪→⎩3.3 Определить область применимости указанного НАМ относительноалфавита {a,b}:⎧ a→b⎪а) ⎨ b → c⎪⎩ c → a⎧a →⎪б) ⎨ bb → b⎪⎩ ccc → cc⎧ * ab → ab⎪ *a →*⎪а) ⎨ * b → *⎪* a⎪→*⎩⎧a →⎪в) ⎨ b → b⎪⎩ c →⎧ ab → ba⎪б) ⎨ ba a ab⎪⎩ b→ bb⎧a⎪bг) ⎨cc⎪⎩c→c→a→→c⎧ aa → baв) ⎨⎩ b →a3.4 Построить НАМ, который из всех слов в алфавите {a,b,c} применимтолько к двум словам – пустому слову и слову abccba.3.5 Построить НАМ, в котором не более 5 формул подстановки и который извсех слов в алфавите {a,b} применим только к словам, имеющим следующий вид:а) anbn, где n≥0б) anbm, где n≠m, n≥0, m≥0в) anbm, где n≥m≥0г) anbm, где n>m≥03.6 Построить НАМ, в котором не более 5 формул подстановки и который извсех слов в алфавите {a,b,c} применим только к тем словам, длина которых:а) кратна 5б) не кратна 5в) больше 4г) меньше 4д) равна 3е) не равна 33.7 Построить НАМ, в котором не более 3 формул подстановки и который извсех слов в алфавите {a,b} применим только к тем словам, для которыхвыполняется хотя бы одно из следующих двух условий: 1) в слове меньше трёхсимволов a; 2) число символов b кратно 3.433.8 Пусть в каждой формуле подстановки некоторого НАМ число символов влевой части строго больше числа символов в правой части.
Доказать, что такойНАМ применим к любому слову.3.9 Определить, самоприменим ли указанный НАМ:а) { →б){a⎧b →a⎪г) ⎨ ab → ab⎪⎩ aa a⎧ a →bв) ⎨⎩b →a⎧ b →aд) ⎨⎩ aa → b3.10 A={a,b}. Построить НАМ, в котором не более 4 формул подстановки икоторый:а) самоприменим и применим ко всем словам в алфавите А;б) самоприменим, но неприменим ко всем словам в алфавите А;в) самоприменим и применим только к какому-то одному слову в алфавите А;г) самоприменим и неприменим только к какому-то одному слову в алфавите А;д) несамоприменим и неприменим ко всем словам в алфавите А;е) несамоприменим и применим только к какому-то одному слову в алфавите А;ж) несамоприменим и неприменим только к какому-то одному слову валфавите А.3.11 A={a,b}. Построить НАМ, в котором не более 3 формул подстановки икоторый:а) самоприменим и применим только к тем словам в алфавите А, которыесодержат хотя бы один символ a;б) самоприменим и неприменим только к тем словам в алфавите А, которыесодержат хотя бы один символ a;в) несамоприменим и применим только к тем словам в алфавите А, которыесодержат хотя бы один символ a;г) несамоприменим и неприменим только к тем словам в алфавите А, которыесодержат хотя бы один символ a.3.12 Пусть в некотором НАМ все формулы являются обычными и есть формулас пустой левой частью.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
