lekcii4 (Лекции), страница 4

являясь вариантом машины К, должна иметь следующий вид: -Ау» 10 о г т.е. ма<пина Л1, осуществляет сдвиг головки на слово над алфавитом А< (оно кодирует букву на ленте исходной машины), а затем просматривает следующую букву на ленте: если она отличается от Л, т.е. следующая буква является кодом какой-то буквы из Ар, то головка возвращается назад, чтобы начало кода буквы (символ Л) попало в рабочую ячейку; если же она равна Л, то эта буква, заменяется Л' (здесь мы учитываем, что лента бесконечна и мы не можем заранее заменить все буквы Л их кодами Л'). Машина М< строится аналогично машине ЛХ„.

Она имеет диаграмму, аналогичную машине Ь: Машина Л1х должна заменять п„на а,, или на Л, Машина Л1„, должна моделировать работу элементарной машины а, т. е, осуществлять такую последовательность тактов: Рагиал, аг,,(Л) Й... ( Л )/... /... а', Л )=~* л„л,л-л м„ ==; [Ла„а,,...а...(Л)!/.../Лй...!...а,, Л) Таким образом, машина, ЛХ должна изменять количество палочек в одном слове, не меняя остальной последовательности слов на ленте. Частные случаи машины ЛХ,, когда л = лил.л, были рассмотрены в примерах 3.4.2 и ЗЛ.З. При построении машины М,, будут использованы машины Я„и Я, построенные в этих примерах. Машина, ЛХ,.

должна заменить на, ленте кодовое слово а,',, словом а.', не меняя остальных слов. Для этого машина Л1„должна, подсчитать количество палочек в слове а;, и, если гь < л, добавить к слову а,', л — гь палочек, если же гь ) 1, стереть в слове а', гь — у палочек. Эти действия может осуществить машина с диаграммой: И= ° г ° г а, 1 гл — г1 — ° ° ° ° г«; — г 2 зл р+л р"Х ! с г Последовательность машин г в верхней части диаграммы представляет собой счетчик палочек в слове а',, (оно может содержать от одной до р + 1 палочек, так как является кодолл буквы ггл„Е Ар).

Если л„< л, то (~ — гь) раз вклпочается машина Я„, в результате чего на ленте высвобождаетсЯ место длЯ 1 — гь палочек; если ль ) 1, то (гь — 1) Раз включаетсЯ машина Я, в результате чего стирается гь — 1 палочек. После того как слово а,'„превращено в слово а', выполняется машина 1', устанавливаюлцая головку на начало слова а'. Таким образом, машина ЛХ„, действительно заменяет код буквы а,„кодом буквы а .

Машина ЛХ . Пусть на диаграмме исходной машины Т символ С был соединен с симвоа, а, а, лами Сл, Сз,..., Сь стрелками вида — -, —, ..., — соответственно. Символам Сл, С2„ ..., Сь на диаграмме машины Тл соответствуют символы ЛХсь ЛХп, „..., ЛХс„.

Эти символы соединяются между собой следующим образом (для определенности мы предполагаем, чтолл<гз« .гл): 1 Л, ! 2 г 1 ° г ° г г х т ° ~ ° ° ~ ° Ф мсг ° ~ мс Здесь последовательность букв г снова представляет собой счетчик палочек в коде буквы„ которая у исходной машины расположена в рабочей ячейке. Узнав, какая буква в рабочей ячейке, мы возвращаемся к ее началу (машина Е) и переходим„если это нужно„ к одной из машин ЛХгл, ЛХое ..

ЛХгл Анализ работы машин ЛХ„ЛХь М, (1 = О, 1,..., р), ЛХ показывает, что машина Т,„ определяемая диаграммой, полученной из диаграммы машины Т заменой символов г, 1„а и стрелок символами ЛХ,, ЛХь ЛХ„, и ЛХ соответствешю, действительно моделирует машину Т цад алфавитом Аь Теорема доказана. Лекция 10 2.5 Вычислимые функции 2.5.1 Понятие функции на множестве слов Пусть А„и А, два алфавита и пусть Е С А",. Функцией из множества, Е в множество Л," называется правилг>. которое каждокгу слову и Е 1.

став>гг и соответствие единственное слово п,' Е Л", называемое значением функции Х на слове и (это значение мы будем обозначать п~ = 7(и). Множество 1' называется областью определения функции 7 и обозначается 7>г'. 7(7). Множество ьсех п~ Е А;, являющихся значениями функции Х на всевозможных словах и Е 1>еЯ), называется множеством значений функции 7 и обозначается Хггг®. Функция 7 определяет отображение 7: Š— ~ А,* множества Е в множество Л;. При этом п. = Ди) является образом слова п,, а множество Хт(7) образом множества 7, при отображении 7. Мы определили функцию одной переменной, или одноместную функцию.

Для определения п,-местной функции напомним понятие декартова. произведения. Декартово произведение М х Аг двух множеств ЛХ и Аг определяется как множество всех упорядоченных пар (т, и), где т, е ЛХ, п, е Л'. В частности, если ЛХ = АГ, то декартово произведение ЛХ х М = ЛХэ представляет собой множество всех упорядоченных пар элементов мно>кества ЛХ. Аналогично множество ЛХ = ЛХ х М = ЛХ х ЛХ можно определить как множество всех упорядоченных троек элементов множества ЛХ и т.д. Таким образом, М" определяется по индукции как множество всевозможных упорядоченных и-ок элементов множества ЛХ.

и;местная функц>ш 7 определяется как отобрпг>гсение 7: Š— А;, где Е С (А,*)". Таким образом, и-местная функция 7 задается правилом, которое каждому элементу Х Е Е С (А",)" (здесь Х -- последовательность из п слов и„иэ,..., и„над алфавитом А,) 75 ставит в соответствие слово и) Е Л,*. Значение и п;местной функции 1 на последовательности слов Х = (и,, и~,...,и ) обозначается и) = 1'(и,, и~,...,и„), Область определения ВеЯ) и множество значений 1)пЯ и;месьгпой функции 1 определяется так же, как и для одноместной функции.

2.5.2 Понятие вычислимости 2.5.3 Функции, вычислимые по Тьюрингу и-местная функция 1: 1. — ) Л,'„1, С (Л',)" может быть определена с помо)цьк) машины Тьюринга. Пусть Т машина Тьюринга с рабочим алфавитом А„таким, что Л, С Лр, Л, С А„. и-местная функция 1т может быть определена следующим образом: последовательность Х = (ид, из,...

и„) Е (А";)"' принадлежит ВеДЯ тогда и только тогда, когда машина '1", примененная в ситуации [ ЛитЛи~... Ли,,(Л)Л >, останавливается в ситуации [Л=Лш(Л)Л >, где в Е Л,*, и' Е Л,*; в этом случае слово и,' е Л,* по опредслснин) является значением фУнкции 1т на РассматРиваемой последовательности Х: и) = 1т(и,, и),..., и„). "1аким образом, М'1' Т соответствует функция 1т. определяемая этой ъ)ашиной. Это позволяет описать действие машины Т, указав функцию (т.

С другой стороны, применяя МТ к различным сообщениям, можно узнать, какие сообщения задают функцию. а какие-- нет. Определение 2.5.1. Функция 1: (А*,.)" — А; называется вычислимой по Тьюрингу (ВТ-функцией), если существует МТ с рабочим алфавитом А.„, содержащим алфавиты А, и Л) (в силу принятого соглашения об алфавитах (см. п.2.6.1) для этого достаточно, чтобы р = шах(а,1)) такая, что функция 1т .

(А„*)" — А,"„определяемая этой МТ, совпадает с 1' ( 1т = 1'). О любой такой Л1Т говорят, что она вычисляет 1'. Из определения 2Л.З в частности, следует, что если МТ Т' моделирует машину Т„то эти машины вычисляют одну и ту же функцию 1. Класс ВТ-функций определяет границы возможностей программирования: лля невычислимых функций составление алгоритма )ювозможек)! 2.5.4 Нормированные вычисления Определение 2.5.2.

Функция 7': (Л,')" — ) Л,* называется нормированно вычислимой по Тьюрннгу (НВТ-функцией), если существует МТ 11, которая вычисляет 1 и при этом удовлетворяет следующим требованиям: 1. если Х = (и), из,..., и„) ф Вс1(1), то машина Т). после применения к Х никогда не останавливается; 2, если Х = (и,, из...., и„) Е Вс ~(1'), то Ту вычисляет значение функции г, [Л Ли)ЛизЛ... Лил(Л)Л > =Ф* [ЛвЛи)Лиз...

ЛидЛ~(им из,... и~)(Л)Л >, -. Е Ар и Останавливается. Смыл)л нормированного вычисления состоит в том, что при таком вычислении часть ленты, расположенная левее символа Л, непосредственно предшествующего и), не меняется и не влияет на работу машины Ту. 1Гри нормированном вычислении головка не должна заходить левее указанного символа Л.

76 Пример 2.5.3. 11усть и и и два непустых слова над алфавитом А = (~): и Е (()*, ш Е ())*. Эти слова можно считать изображениями натуральных чисел, сопоставив натуральному числу и слово пад (!)*, содержащее п палочек: у(//... )) = и, 11остроим МТ Р., реализующую нормированное вычисление функции г"(и, и.) = ии1 (через пш обозначено произведение натуральных чисел, изображаемых словами и и и)).

Действие машины Р можно описать следующим образом: г (Л=.ЛиЛш(Л)Л >==~* (ЛзЛпЛи<Лип(Л)Л > При вычислении иии машина Р нс должна заходить в ячейки части ленты, обозначенной ~Л~, и в частности не должна менять записи в этой части. Для этого мы поместим непосредственно слева от слова. и специальный символ Ф (он будет обозначать гранину доступной части ленты). Это можно сделать, применив машину Т. = 1,2Ф. Далее будем просматривать слово и, и копировать слово и) столько раз подряд, сколько палочек содержится в слове и. Это действие может быть реализовано машиной э к.г. 2 3' ° — — — -1 Т 2 Машина Т2 стирает слово и, поэтому после ее работы необходимо восстановить это слово. а, также убрать символ Ф, заменив его несобственной буквой Л, и поместить головку непосредственно справа от результата. Эти действия поможет выполнить машина 1 3 ~ ° Я.

Объединяя диаграммы машин Тн Тгп Та, получил диаграмму магнипы Р, реализующей нормированное вычисление функции 1(и, и,) = пи~: Ф М р ° ° ( ° а ° г 2 77 Всякая НВТ-функция является в то жс время и ВТ-функцией. Это следует из определения 2.4А. Оказывается, что верно и обратное утверждение, т. е. имеет место следующая Теорема 2.5.4. Всякая ВТ-функция является НВТ-функцией, причем соответствующая МТ не использует никаких вспомогательных букв.

Доказательство этой теоремы будет приведено в п. 2.7А, так как машину Тк, которая нормированно вычисляет ту же функцин> 1т, что и мап>ина, Т. удобно строить, используя методику, которая будет описана в разделе 2.6. Теорема 2.5.5. Для лк>бой машины Тьюринга можно эффективным образом построить машину Ту, которая имеет ленту, не ограниченную только с одного конца„и которая моделирует машину Т. г Теорема 2А.4 является простым следствием теоремы 2.4.3. В самом деле, если машина Т вычисляет функцию ~т, то в силу теоремы 2А.З можно построить машину. Тм, которая нормированно вычисляет эту функцию и, следовательно, моделирует машину Т.