lekcii2 (Лекции)

Тпг, если машина Тпг записала знак И (истина), то он стирается, после чего включается машина Х, формирующая заключительную ситуацию ~Ли~~Лгю~Л... Лге,,ЛДшн ша,..., и,„)(Л)Л > Если маапина Тпр записала знак Л (ложь), то включается машина Т, которая никогда нс останавливается. Для завершения конструирования ма~пины Т~~ осталось разработать схемы машин Тгзд, Тсж, Тпг, Т и Х.

При конструировании этих машин мы будем предполагать, что рабочий алфавит машины Т~ содержит буквы ам аа,..., аь Машина, Трзд описывается следующей схемой: 3 Х1 ° Г ° 1~еЯе~ ° При составлении схемы машины Трзд использованы символы машин 1 ~, Лз и Р„. Машина 1 „~ сдвигает головку влево до тех пор, пока нс встретится ячейка со знаком ф: ее схема имеет вид ° 1, ! Ф Машина Йа сдвигает головку вправо до тех пор, пока нс встретятся три подряд идущие ячейки со знаком Л; схема этой МТ имеет вид Я~ г ° 2 Х 2 Машина йз сдвигает головку вправо до тех пор, пока не встретятся две подряд идущие пустые ячейки; она описывается схемой 99 + ~ ° Машина Р,.

«освобождает» ячейку за очередной буквой; ес схема записывается в виде г ° а1 ° Э Я ° Машина Тсж производит действие, обратное действию машины Тнзд. Ее схема может быть представлена в виде Машина, Тож сначала стирает все буквы на ленте, расположенные правее значения функции ~, вычисленного машиной Т', потом заменяет знаки, расположенные между буквами слова, являющегося значением функции г, символом Ф и в заключение придвигает буквы, составляющие значение функции ~, вплотную одну к другой, пока не будут стерты все ф.

Схема машины Р~. 100 а — ~Ф з ' ..†.— — -Ф е ! ° а ° ! ° а ° ! ° а ° Машина Тпр просматривает слово, вычисленное машиной Х~ в качестве значения функции 1", и убеждается в том, что оно нг содержит букв, не входящих в рабочий алфавит машины Т>. Приведем схему машины Тпр: ° ! ° .; — —.-------» ! ° х ,- -» г ° г. ° а1 а1 — Ф ° !э> ° г ° г ° --— 'г ° г с Машина Т, реализует бесконечный цикл. Она начинает работать в тех случаях. когда аргументы не принадлежат области определения функции 1'.

Машину Т' можно задать безусловным зацикливанием пары т1. Действие машины Х состоит в том, чтобы поместить вычисленное значение функции 1 непосредственно вслед за ее аргументами, расположенными на левой части ленты (т. е. левее Г 71), убрав с ленты все «лишние» знаки. Похожая машина была сконструирована при рассмотрении примера 2.7.1.

Построение схемы машины завершает процесс конструирования машины Т . н 2 Ф Ф вЂ” «! ° ~аде!« — м!' ° е ° ° ° ! ° еЯ» ,' Ф ! 101 В заключение сконструируем машину Т~, которая нормированпо вычисляет функцик> /, не используя при этом дополнительного знака ф. Для этого воспользуемся второй теоремой Шеннона. 1!рименив конструкци>о рассмотренную при доказательстве этой теоремы (см. и. 2.4А) к манчино Т~~, получим машину Т'>', моделирующую машину 'Г~ над где Г - кодирующая машина, которая по исходной последовательности слов на ленте строит последовательность кодов этих слов над алфавитом А,: [Лил Л...

Лю„(Л)Л >==~ [Ли1~Л... Ли1„ЛЛи~1 Л... Ли,(Л)Л >, а Е декодирующая МТ., которая по коду значения функции 1 восстанавливает это значение в исходном алфавите: [Лги~Л... Лил,ЛЛи гЛ... Ли1„,Лиэ(Л)Л >=~* [Лип... Ли,'„Ли~(Л)Л ) Схема машины Г„имеет вид: 7 Рк К 1,' 12 гд1'. каждая из магпиг1 ~'„коди1эует ~-й аргумент: [ЛийЛ... Л1и,ЛЛИ'(Л)Л >=~* [Л1и1... Ли~„ЛЛУ'ю,Л(Л)Л ) Схема машины К, такова: п-1'+2 а1 еяе ,М ~П-1+~ 2 п-1+2 В г ° (, ° г ° ) 1.2.(-а ° г-, П-1+2 ° Й.

В2 г °, ° г ° ", а1 П-1+2 "й ° 1~-1 п-1+2 В2 ° г ° (; ° г ° ) ~ ° 1 ° а ° г В схеме машины К, символы йэ и Ьэ обозначак1т МТ, которые сдвигакгг головку вправо (соответственно влево) до тех пор, гкэка пе встретятся две подряд идущие пустые ячейки. Схемы этих машин соответственно имеют вид: ° й ° г ° [ ° ;Ф - .---н [ ° [ ° ° г ° 4 102 алфавитом Лг = (~). Отметим, что машина Т~ использует в своей работе всего две буквы: ~ и Л. Машину У Х~ можно описать с помощью следующей схемы: р„т е Построим схему декодирующей машины Е. Ке можно представить в виде Е с г 1Ьл1 ~,г1 ллг[0К В схеме машины Е символы Йлл и 1,о, представляют МТ, стиранлцие последовательность слов справа (соответственно слева) от головки: нлх [ЛИ'~ЛИЛ(Л)И2Л >=~* [ЛИ~Ли.ЛЛ... Л(Л)Л >, [ЛИ1Ли~(Л)Л >==~'" [Л(Л)Л...

ЛЛи~ЛЛ > П - символ МТ, восстанавливающей буквы рабочего алфавита машины Тг по их кодам над алфавитом А~ .. [ЛЦ)Л... ЛшЛ!Л >~* [Л!и(Л)Л > Х~ символ МТ, помещающей декодированное слово иб являющееся значением функции 1, непосредственно вслед за ее аргументами: Л~ [Л!п~(Л)Л >==~* [Лш(Л)Л > Машина Ь описывается схемой Она сдвигает головку влево до первой непустой ячейки. Аналогично можно определить машину П с помощью схемы ° ~' ~' а Схемы мал!ив К;о, и 1хх соответственно имеют вид: где через Лл и Лл обозначены МТ, стирающие одно слово справа (соответственно слева) от головки; эти МТ описываются схемами: е бТ--....Фа~, ° Для того, .чтобы закончить описание машины Е, приведем ес схему; 103 .-в т, г ° — — + 1 г а 2 й х г'г — х г' ° 1. ° г»а и схему машины Ж,: ° ~ ° 4 ° 1 ° г ° "„° г $ ,'1 ~ ~„° ~ ° я е г2в' Я 11а этом завершается построение машины Т' и доказательство теоремы о нормированной вычислимости.

2.7.5 Некоторые фундаментальные результаты теории алгорит- мов Результаты, получг нные Харелом, Цейтиным, Колмогоровым и др. ~7, 4, 31~ Лекция 14 2.8 Развитие алгоритмической модели Тьюринга 2.8.1 Понятие об универсальной машине Тьюринга Ранее нами рассматривались МТ, каждая из которых выполняла свой строго определенный алгоритм: разньн-: алгоритмы выполнялись разными машинами Тьюринга.

Однако можно построить МТ, способную выполнить лк)бой алгоритм, сымитировав работу соответствующей М1'. Такая маслина "!'ьюринга называется универсальной. Построение униесрса.льной машины Ттиорвнга один из ваэкнейших для программирования результатов теории алгоритмов ~7~. До начала работы универсальной МТ на ее ленту записывается последовательность четверок, представляющая программу машины, работу которой необходимо выполнить, и начальные данные. Универсальная МТ просматривает программу, записанную на ес ленте, .и выполняет команду за, командой этой программы, получая на ленте вслед за 104 аргуъ<ентами р<т>ультат вычислений. Текст программы <в виде последовательности четверок) помещается на ленте слева, от аргуъ<ентов и, следовательно, при нормированных вычислениях сохраня<тся неизъ<е>п<ым в процессе выполнения программы.

Реализация универсальной ъ<ашины Тьюринга представляет собой весьма непростую задачу. Фактически <>на была, осуществлена при доказательстве теорем Шеннона, когда строились машины Тьк>ринга> моделирующие любые другие МТ. Исследователем низкоуровневых алгоритмических моделей Дж, Тромпом ~96~, пре1<:<ожив>ням комбинаторнологическук> модель (С1~), объем двои <ного микрокода УМТ оценивает<.я в 40 КБайт (против 2 КБайт для С1-модели>. Построение универсальной МТ показало принципиальную возможность аппаратной реализации автомати <еского устройства, выпол><яюп<его любые аягоригпъ<ы ио их описа><пям. (Аппаратной реализацией какого-либо устройства мы называем построение этого устройства не на бумаге — в виде описания или проекта, а в виде реально работающей аппаратуры, т.

е. механизмов и приборов). Построив аппаратуру универсальной М'1', мы получили бы возможность автоматического решения задач обработки данных: для решения каждой такой задачи было бы достаточно составить соответствуюшую программу (алгорить<) и поместить ее в виде последовательности четверок вместе с начальными данными на ленту универсальной МТ.

Однако, поскольку мы уже убедились в неудобстве низкоуровневого программирования МТ, было бы желательно построить более удобную для человека диаграммную (точнее, схеъ<ну<о) версию УМТ. В и. 2.7 было показано, что программу МТ удо<лю составлять «сверху вниз» в виде последовательности схем. Каждой такой последователыюсти схем соответствует программа МТ в виде совокушюсти четверок, причем эта про>рамь<а может бьггь эффективным образом построена по соответствующей последовательности схем [4~. Однако вы>юлнять такое гюстроение вручную очень сложно, да и не нужно, поскольку нетрудно составить алгоритм, реализующий это посзро<ни<,.

Для составления указанного алгоритма необхотиъ<о прож><с в«>го на>у~<иться за>писывать схемы МТ на ленте (ведь схемы, точнее говоря, их описания, представлян>т сооой н<>~<альнь>е данные рассмагриваемого универсальш>го алгори гъ<а). 11одобная процедура уже рассматривалась при доказательстве эквивалентности диаграмм и программ. В об>цем случае под универсальностьк> понимают способность некоторой системы моделировать работу любой другой си<'темы, когда, описание последн<й подается ей на вход в закодированном виде.

Это опр<'.д<;ление н<>является виол~с строгим, по<>кольку н<. указывает<я, какие способы кодирования являются допустимыми. Можно определить кодирование такиъл образом, что оно будет включать в себя все вычисления, производимые моделируемой систеълой -- разумеется, такой способ кодирования следует признать и<допустимым. Однако в большинстве случаев допустимость выбранного способа кодирования можно оценить с точки зрения здравого смысла.

В следующиъл параграфе будет приведен пример кодирования машин Тьюринга. Доказать универсальность некоторой системы .-- значит показать, что она может моделировать поведение некоторой системы, универсальность которой доказана, либо целого класса систеь<, который является универсальныь< (иаприъ<ер, всех машин Тьюринга).