lekcii2 (522346), страница 2
Текст из файла (страница 2)
В 50-60-х годах прошлого века был сделан ряд открытий, связанных с универсальными машинами Тьюринга. Было доказано, что никакая машина Тьюринга с 2 состояниями и 2 буквами алфавита не может являться универсальной. Марвин Минский построил универсальную машину Тьюринга с 7 состояниями и 4 буквами алфавита. В течение долгого времени не было получено серьезных усилений этого результата. 105 Новый толчок изучению машин Тьюринга с малым числом состояний и букв алфавита придали исследования Стивена Вольфрама ~105~. Он заметил, что системы., описываемые весьма простыми правилами, могут вести себя достаточно сложным образом. В частности, он предположил, что всякая простая система, поведение которой не является достаточно простым, является универсальной.
Вольфрам построил универсальную машину Тьн>ринга с 2 состояниями и 5 буквами алфавита, Он также пап<ел 1Л машин Тьюринга с 2 состояниями и 3 буквами алфа,вита,, имеющих эквивалентное поведение, которое ему не удалось проанализировать до конца. Стивен Вольфрам и его единомьппленники предлагают приз в 25000 долларов за ответ на вопрос, является ли одна из этих ма>пин универсальной. Она имеет множество состояний (до, <>д), алфавит 1ао,ад, аэ) и описывается следующими правилами: (<Ло, ао, а>; г,<Л>) (<1о, а>, а2, <, 1о) <<Чо, а<ь а>, 1, <7о) (<1> ао.,аг,1,<1о) (<1>, а> > .а>ь т,.
<» ) (<7> а2 ао г><1о) 2.8.2 Линейная запись схем машин Тьюринга Трудность записи схем МТ на ленту состоит в том, что схемы двумерны, в то время как на, ленту можно пол<естить лишь линейную запись. Та,ким образом. возникла задача линеаризации записи схем. Главным в этой задаче яш<лется не запись на ленту «цифровой фотогра<1»<и» двумерной схемы МТ, а получение структурно-топологического, «векторного» представления.
Элементы такого щ>едставления мы уже получали при доказательстве эквивалентности диаграмм и гц>ОГ1замм. В и. 2.7.2 было отмечено, что схемы допускают всего три вида сочетаний составляющих их ХЛТ: композицин>, ветвление и цикл. Рассмотрим, как можно линеаризовать каждое из этих сочетаний. Ка<<нозиц< л состоит в последовательном выполнении нескольких действий, представленных в схеме символами соответствующих МТ.
Эта часть записи схемы и так линейна,, так как в случае композиции символы указанных МТ просто выписываются один за другим. Ве>веление изображается фрагментом схемы, который имеет вид Здесь левая точка описывает состояние <>, в котором происходит ветвление. Буквы а>, а2,..., аь вместе с состоянием <> <образу.ют определяющие пары, указывающие, какая из ветвей должна быть выбрана. Символы о'>, о2,..., Я, представлян>т собой фрагменты схемы,. описывающие, какие действия должны быть выполнены в каждой из ветвей. Правая точка определяет состояние <1' после ветвления. 106 В линейной записи рассматриваемый фрагмент схемы будем представлять в виде 1К а~? '~~ [~ а2? бг 0 .
0 аь'? ~ь 1"1 1Е и Е1 соответственно обозначают начало и конец ветвления (состояния д и ц' соответственно). Знак «?» отделяет букву, надписанную над стрелкой, от фрагмента схемы, который описывает действия в соответствующей ветви. Символ Ц отделяет одну ветвь от другой. Цикл изображается следующим фрагментом схемы: Первая и последняя точки в этом фрагменте соответствует состояниям ц (начало цикла) и д' (конец цикла). Буквы ан а2,..., аь вместе с состоянием ц составляют определяющие пары, по которым цикл должен быть продолжен (при этом выполняется одно из действий, описываемых фрагментами схемы Яы о2,..., Ьь).
Буквы, отличные от аы аэ,..., аь, вместе с состояниеги д формируют определяющую пару, задающую выход из цикла (переход в состояние д'). Средняя точка тоже соответствует состоянию д (она введена в схему лишь для удобства). В линейной записи описание цикла имеет вид РО а~?Я~ [~ а~?оэ [~ ...
[~ аь?»ь О11 РО и ОР обозначают соответственно начало и конец цикла, а знаки '? и Ц имеют тот же смысл, что и в случае ветвления. 2.8.3 Язык описания схем машин Тьюринга Правила линейной записи схем МТ составляют основу языка описания схем, названного ОСТ (Описание Схем Тьюринга). Рассмотрим два примера описаний конкретных тьюринговых схем на языке ОСТ, вводя попутно некоторые конструкции этого языка. Пример 2.8.1. В качестве первого примера, рассмотрим описание программы машины Кэ, выполняющей копирование третьего слова слева от головки. Будем считать, что слова на ленте МТ заданы над алфавитом А = 10, 1, 2, 3, ..., 91. 107 Название ХГ!' на языке ОСТ может быть любым словом из русских и латинских букв, арабских цифр и знаков *, 1, —,,~, (, ), П, (о).
Требование линейности записи исктпочаст возможность использования индексов, .так что машину Кз назовем КЗ. Также будем писать 1.*'"4 вместо 1.4. 11рограмма магпины КЗ на, языке ОСТ имеет следующий вид: МТ КЗ; "ПОСЛЕДОВАТЕЛЬНОСТЬ ЗНАКОВ, ЗАКЛЮЧЕННАЯ МЕЖДУ КАВЫЧКАМИ, НАЗЫВАЕТСЯ КОММЕНТАРИЕМ К ПРОГРАММЕ И МОЖЕТ БЫТЬ УДАЛЕНА ИЗ ПРОГРАММЫ БЕЗ ИЗМЕНЕНИЯ ЕЕ ЭФФЕКТА. МТ ПЕРЕД ИМЕНЕМ ПРОГРАММЫ вЂ” УКАЗАТЕЛЬ НАЧАЛА ОПИСАНИЯ, КОНЕЦ ОПИСАНИЯ УКАЗЫВАЕТСЯ КАК Е)Ч1)." ВЕС1Х АЬРНАВЕТ: О, 1, 2, 3, 4, 5, б, 7, 8, 9; '*ОПИСАНИЕ ВНЕШНЕГО АЛФАВИТА МАШИНЫ КЗ" МТ Ь; "ОПИСАНИЕ МТ, СИМВОЛ КОТОРОЙ ИСПОЛЬЗУЕТСЯ В ПРОГРАММЕ МАШИНЫ КЗ" ВКС1Г«1 АЬРНАВЕТ: О, 1, 2, 3, 4, 5, б, 7, 8, 9; 1; 1)О () ~ ? 1 О1); "ЗНАК ПРЕДСТАВЛЯЕТ В ОСТ ЗНАК ПРОБЕЛА Л" К«11) 1.; "КОНЕЦ ОПИСАНИЯ МАШИНЫ 1." МТ Н; ВКС11Ч А1РНАВЕТ: О, 1, 2, 3, 4, 5, 6, 7, 8, 9; г; 1)О ()7«? г О1Э; ЕХБ Н; 1 ~:~3 1)О О? а( ); Н««4; а(0); Ь~«4; а(0); г П 1? а( ); Н««4; а(1); Ь4«4; а(1); г П 2? а( ); Н«44; а(2); 1.««4; а(2); г П 3? а( ); В««4; а(3); Х.««4; а(3); г П 4? а( ); Н««4; а(4); Ь««4; а(4); г П 5? а( ); Н4«4; а(5); Ь«44; а(5); г П б? а( ); Н««4; а(б); Ь««4; а(6); г П 7? а( ); Н4«4; а(7); Ь««4; а(7); г П 8? а( ); Н««4; а(8); Ь««4; а(8); г П 9? а( ); Н444; а(9); Ь«-~4; а(9); г ОП; Н~ «'3; К)Ч1) КЗ Пример 2.8.2.
Описание на языке ОСТ программы машины С«10ЖДР, выполняющей сложение двух обыкновенных дробей, в десятичной позиционной системе счисления. Каждая из дробей-слагаемых линейно записывается на лепте в виде слова и = и««н, где п и и пепустые слова над алфавитом 10, 1, '2, 3, 4, 5, 6, 7, 8, 91, представляющие соответственно числитель и знаменатель дроби, слово «содержит хотя бы одну цифру, отличную от О. Для описания программы машины С<10)КДР потребуются МТ, выполняющие арифметические действия пад целыми числами, МТ, копирующие слова на ленте, и некоторые 108 другис М'1'.
Описания программ этих МТ может быть включено в состав рассматриваемой программы, либо заранее помещено на свободную (левую) часть легггы, В последнем случае описание соответствующей МТ в тексте программы заменяется описателсм ЫВ, который означает, что соответствующую МТ нужно искать в левой части ленты, 11рограмма С~1ОЖДР может быть записана следующим образом: МТ СЛОЖДР; ВЕС1Х А1РНАВЕТ: О, 1, 2, 3, 4, 5, 6, ?, 8, 9, / МТ ЧИСЛ; ЫВ; "ВЫДЕЛЯЕТ ЧИСЛИТЕЛЬ ДРОБИ" МТ ЗНАМ ; ЫВ ; "ВЫДЕЛЯЕТ ЗНАМЕНАТЕЛЬ ДРОБИ" МТ ДРОБЬ; ЫВ "СОСТАВЛЯЕТ ДРОБЬ ПО ЧИСЛИТЕЛЮ И ЗНАМЕНАТЕЛЮ" МТ К2," ЫВ МТ КЗ; ЫВ МТ К4; ЫВ МТ К5; ЫВ МТ Кб; ЫВ МТ К10; ЫВ МТ К ; ЫВ ; "КОПИРУЕТ СЛОВО" МТ НН ; ЫВ ; "ВМЕСТЕ С МАШИНОЙ КН НОРМИРУЕТ ВЫЧИСЛЕНИЯ" МТ КН ; ЫВ ; "ВМЕСТЕ С МАШИНОЙ НН НОРМИРУЕТ ВЫЧИСЛЕНИЯ" МТ+; ЫВ МТэ; ЫВ МТ вЂ”:; ЫВ; МТ НОД ВЕС11Ч А1РНАВЕТ: О, 1, 2, 3, 4, 5, 6, ?, 8, 9; МТ-; ЫВ МТф; ЫВ МТ>; ЫВ НН; ф; РО И? К2~~2; 1Р И? К2~~2; — ; К2; ф П Л?К; КЗ; Р1 ОР; КН; Ег"1О НОД; НН; К2; ЧИСЛ; К2; ЗНАМ; К5; ЧИСЛ; К2; ЗНАМ; Кб; К2; э ; К10; К4; 4 ; Кб; К10; 4 ; К4; К2; + ; К10; НОД; †; ; К4; КЗ; †: ; К4; ДРОБЬ; КН; Е1ЧП СЛОЖДР Лекция 15 109 2.9 Модель фон Неймана 2.9.1 Критика модели вычислений Тьюринга Рассмотренные примеры программ на, языке ОСТ показывают, что этот язык вряд ли можно считать удобным и эффективным средством описания алгоритмов.
Описание программы, выполняя>щей несложный алгоритм сложения двух обыкновенных дробей, заняло страницу, а ведь оно было приведено далеко нс полностью: почти все МТ, через которые описывается алгоритм, были объявлены «библиоточными (описатель 1 1В), т. с. уже составленными при описании других алгоритмов и записанными на свободной части ленты. На самом деле такое предположение справедливо лишь для копирующих МТ (машин К„при различных и) и для МТ НН и КН, обеспечиван>щих нормирование вычислений. Описания программ всех остальных МТ должны быть наряду с описанием программы НОД включены в программу явно, что, как легко видеть, увеличит се текст примерно втрое.
Второй существенный недостаток языка ОС"Г - необходилюсть А«иогонисленных копирований. Если внимательно просмотреть описания МТ СЛОЖДР и НОД, можно заметить, что копирования составляют около половины всех действий, выполняемых при работе соответствующих МТ. Частые копирования не только резко увеличивают время выполнения программы, но и вызывают трудности при ее составлении; каждое слово присутствует на ленте в нескольких экземплярах, что усложняет проблему поиска нужных слов при составлении программы.
В программе СЛОЖДР было употреблено семь разных копирующих мап>ин: К, Кг, Кг, К«, Км Ка, Кш. Ясно, что количество таких машин потенциально бесконечно. Существенным недостатком языка ОСТ является также необходимость при составлении программы на эп>ом, языке вьтисывать ситраиии на ленте, так как если этого пе делать, то можно легко запутаться в расположении данных на ленте, что приведет к ошибкам при составлении алгоритма. Все перечисленные недостатки языка. ОСТ обусловлены свойствами машины Тьюринга, т. е, модели вычислений, на основе кс>торой разработан этот язык. Громоздкость описаний обусловлена тем, что М'Г осуществляет б11квальную обработку данных, т. е, длина описания программы пропорциональна числу букв сообщения, просматриваемых при выполнении алгоритма.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
