lekcii5 (Лекции), страница 11

Этому способствовали свойственные многим гениальным людям странности и чудачества в характере самого 'Гьюринга. Они же и привели к его трагической гибели от своеобразной английской рулетки: смешивая различные химические вещества он случайно получил яд и принял его Вовнутрь. 40 2.1.3 Нормальные алгоритмы Маркова асЫ 1 е.1 '1' = <ас]с] е.1> '0'; е.2 '0' = е.2 '1'; — '1' Ф >1 » 1> >Π— 0> > » < 1« — 0 0<ь 1 < ь-» 1 — »> 2.1.4 Тезис Тьюринга-таверна Использование алгоритмических моделей опирается на тезис Тьюринга-С1ерча о том, что всякий интуитивный алгоритм может быть выражен средствами одной из алгоритмических моделей. Опровергнуть этот тезис пока никому не удалось.

«Доказательством» же тезиса Тьюринга вполне может служить конструктивное построение фон Е!еймановской модели из '1'ьюринговской, предлагаемое в этом разделе курса. Существенно, что все алгоритмические модели описывают один и тот же класс процессов обработки сообщений. Доказано, что одни модели сводятся к другим, т. е, всякий алгоритм, описанный средствами одной модели, может быть описан и средствами другой. Наиболее близкой к вычислительным малпинам является алгоритмическая модель Тькь ринга. Поэтому именно эту модель мы выберем для формализации понятия алгоритма. ' Вы ъюжете больше узнать про личность академика А. А.

Маркова у профессора В. К. Титова, который выполнил диплоъшую работу па мехмате МГУ под его руководством. Алгоритмы Маркова предложены в 1950 г. нашим соотечественником академиком А. А. Марковым' (ълл.~ ]17, 251 На этой концепции основан оригинальный алгоритмический язык Рефал, предолженный в 1976 г. сотрудником Института Прикладной Математики В.

Ф. Турчиным, ныне профессором Ньюьйоркского университета. В. Ф. Турчин известен как составитель культовых сборников «Физики шутят» и «Физики продолжают шутить», в которых остроумие Турчина достигает таких же высот, как и его концептуальное кредо, изложенное в монографии [81~. Концелтпия НАМ и Рефала настолько ортогопальна тьюринговой и другим опсрационньлъл ъюделям, что она, непременно цитируется в научных статьях и упоминается во всех курсах информатики. В настоящее вреъля язык Рофал продолжает развиваться, в частности, в 2001 — 2003 гг, аспирант кафедры 806 М. А. Левинская, выполняя диссертационную работу на соискание учелюй степени кандида,та физико-ълатеълатических наук, предложила и успешно реализовала древовидное расширение Рефала ]981.

На леклцллл деълонст]зи1»устоя приъле]л но]зълальнлзго алгоритъла Ма])кона и эквивалс.нтная ему программа на Рефале прибавления 1 к десятичному числу (алгоритъл раоотает не с самим числОм, а с: Оуквами его цифрового изОО]за>кения 2.2 Машины Тьюринга 2.2.1 Неформальное описание Машина Тьюринга состоит из ограниченной с одного конца бесконечной ленты, разделенной на ячейки, и комбинированной читающей и пишущей головки, которая может перемещаться вдоль ленты от ячейки к ячейке. В каждой ячейке ленты может быть записан один знак алфавита А., называемого рабочим алфавитом МТ, либо пробел (его мы бучем обозначать знаком Л).

Головка МТ в каждый момент времени располагается над одной из ячеек ленты, называемой рабочей ячейкой, и воспринимает знак, записанный в этой ячейке (букву алфавита А или Л). При этом головка находится в одном из конечного множества (т!ть ттт,..., ц,) дискретных состояний, среди которых выделено одно начальное состояние тттт. В зависимости от состояния, в котором находится головка, и от буквы, записанной в рабочей ячейке, МТ выполняет одну из команд, составляя>щих ее программу. Выполнение команды состоит в выттолнепии элементарного действия, предписываемого этой командой, и переводе головки в новое состояние !которое, в частности, может совпадать со старым). Определено три вида элементарных действий: сдвиг головки на одну ячейку влево (если считать, что лента МТ ограничена слева, то для крайней левой ячейки сдвиг влево не определен), сдвиг головки на одну ячейку вправо, запись в рабочую ячейку какой-либо буквы рабочего алфавита А либо пробел (ттри этом буква, которая была записана в рабочей ячейке до выполнения записи, стирается).

Таким образом, каждая коьлаттда может сменить рабочуто ячейку, сделав новой рабочей ячейкой одну из соседних ячеек старой рабочей ячейки, или, не меняя рабочей ячейки, изменить знак, записанный в рабочей ячейке, и изменить состояние головки. Перед началом работы МТ па ее лепту записывается исходное сообщение так, что в каждуто ячейку летггы записывается одна буква сообщения, либо пробел. Ьудучи конечным, лк>бое сообщение занимает котточнос число ячеек ленты. При этом ячейки, расположенньи. справа, от последней буквы исходного стх>бтттения, заполняются пробелами и считаются тт!тстаьтмть В начале работы МТ ес головка приводится в начальное состояние тта и помещается над начальной рабочей ячейкой, которая определенным и фиксированным д тя каждой ковкретввоб ЛП' образом расположена относительно исходного сообщсния.

Обычно в качестве рабо тей ячейки мы будем брать ячейку, .расположенную вслед за исходным сообтттением, то есть, ячейку, содержащую символ пробела Л, расположенную непосредственно справа от пс>следней буквы сообщения (все ячейки, располо>кенньтт справа от начальной рабочей ячейки, содержат в начале работы МТ символы Л). Пара (т>ш а), где т>а — начальное состояние головки, и е алфавиту А 0 (Л) буква, записанная в начальной рабочей ячейке, определяет команду программы МТ, которая должна быть выполнена первой. В результате выполнения этой команды образуется новая пара (тт, а'), где тт -- текущее состояние головки, а' -- буква, записанная в текущей рабочей ячейке, которая определяет следуюшую команду и т.

д. Таким образом, работа МТ тю шостью определяется ее программой и сообщением, которое было записано па ленте ттеред началом работы МТ. Каждая команда МТ описывается упорядоченной четверкой символов (т!, .а, и, т!'), где ° д Е ~ -- символ текущего состояния головки; ° а Е А 0 (Л) буква, записанная в текущей рабочей ячейке: ° и Е (1., г) 0 А т.т (Л) символ выполняемого действия (и = 1 означает сдвиг головки влево, н = г сдвиг головки вправо, а и Е Ат т(Л) запись соответствующего знака в рабочую ячейку). ° д' Е ст силтвол состояния, в которое команда переводит головку. Пара (т/, а) определяет, какая из команд программы МТ должна быть выполнена (предполагается, что программа содержит не более одной команды, начинающейся с пары И,аИ 2.2.2 Математически строгое определение 00, , †,00 00, †,т,ОО 00,~,1,00 00,1,/,00 00,/, ,01 01, ,т,00 00, , †,п,00 00, †,т,п,00 ОО,т,1,п,00 00,1,/,п,00 00,/, ,т,ОО 1та программа сочетает кувырок палочки с ее продвижением вперед, фактически выполняя примитивную анимацию почттл по Диснею: инерция человеческого зрения домысливает эти рывки до тюлноценных кульбитов.

Поскольку начальное состояние совттадает с конечным, эта программа никогда не останавливается. В силу универсальности пятерок соответствующая МТ имеет вообще только одно состояние. Мы еще вернемся к этим программам после изучения теорем Шеннона, который показал ттезавершттлтость программ машин Тьюринга с одним состоянием. Хотя эти примеры иллюстрируют необходихлость дополнительных команд, а, следовательно, и состояний при программировании в четверках, все же можно составить аналогичный пример программы МТ в четверках с одним состоянием: 00, , †,00 00, , †,п,00 Определение 2.2.1.

Машиной Тьюринга называется упорядоченная четверка объектов Т = (А, ст, Р, ттт), где Т вЂ” символ МТ, А — конечное множество букв (рабочий алфавит), ят конечное множество символов (имен состояний), т/с имя начального состояния, Р - множество упорядоченных четверок (т/, а, и, ц'), т/, ц' Е ст, а б А0(Л), .и Е (т, г1стАО(Л) (программа), определяющее три функции: функцию выхода Рт. Я/ э А — А (А А т.т (Л)), функцию переходов Рч; Я * А — ф и функцию движения головки Г„: с„т э А — ~ (т, т, а) (символ в означает, что головка неподвижна).

За.мечаттие. Первоначально программы машин Тьюринга задавались наборами пятерок, включавших как функцию выхода, так и функцию движения. В частности, Шеннон доказывал свои знаменитые теоремы именно в такой форме записи. В пятерка,х движение головки и запись буквы дополняют друг друга, а в четверках они являются взаимно исключаютттихти действиями.

Кроме того, сутцествуют и другие способы задания программ Тьктринга (диаграммы состояний, таблицы переходов). Рассмотрим рсализацинт одной и той же программы в четверках и пятерках. Программа 2.1. Пример бесконечной анимации ОО, †,Л,ОО ОО,Л,!,ОО оо,!,/,оо оо,/, ,оо 00, †, ),п,00 00, 1,),Н,ОО 00,1,/,Н,ОО 00,/, ,Н,ОО Но в этом примере пришлось пожертвовать движением и вместо кувыркающейся палочки мы получили вращающуюся на месте крутилку, используемую в ОС Н1Х11Х для текстовой индикации выполнения некоторого процесса. Определение 2.2.2.

Ситуацией (или состоянием ленты) называется упорядоченная пара объектов,5' = (=, й), где о' имя ситуации, ' сообщение, записанное на ленте, неотрицательное целое число, равное расстоянию (в ячейках) от края ленты до рабочей ячейки. Иными словами, Л' фиксирует положение рабочей ячейки на лепте. Иными словами, ситуация это Все "1ТО записано на лент1'. с Выдс.Ленной рабо'1ей я'к:Й- кой. Очень удобно следующее нагляднск обозначение для ситуации (линейная запись!): Я = 1111) и,, ., . и,„, (111„)а;„„... Н)„Л), где ( -- край ленты, а), Е А) ) (Л), ...

— пропущенные знаки, скобки () выделяют рабочую ячейку, ) бесконечш>1Й правый край ленты, образованный пустыми ячейками. Определение 2.2.3. Конфигурацией называется упорядоченная пара обт>ектов С = (о, г/), где .5' текущая ситуация, )1 текущее состояние головки. Для конфигурации будем использовать обозначение С = ~ана,,,...а,„,(У.,111,)а„„,...ОК,Л). Каждая конфигурация С однозначно определяет команду МТ, которая должна быть выполнена. После выполпеш)я указанной команды получается новая конфигурация С', про которую говорят, что она непосредственно следует за конфигурацией С: обозначение С =~ С', где ~ — символ бинарного отношения н1>посредственного следования. Отно)ПЕНИЕ Н11К)СРСДСТВ1)ННОГО СЛЕДОВВНИЯ ВЬ1ПОЛНЯ1>ТСЯ И ДЛЯ СИТУВЦИЙ > И О', СООТВЕТСТВУК)- щих конфигурациям С и С', сто мы будем обозначать 1) => .')'.