Реферат: Алгоритмические машины

 

4. Алгоритмическая машина Тьюринга

Машина Тьюринга (Turing machine) получила свое название по имени английского математика Алана Тьюринга, предложившего в 1937 г. способ формального задания алгоритмов с помощью некоторой абстрактной машины. Суть работы сводится к следующему. Имеется потенциально бесконечная лента, разбитая на ячейки, в каждой из которых может быть записан один символ из некоторого конечного алфавита. Машина Тьюринга имеет головку чтения/записи, которая позволяет прочитать символ в текущей ячейке, записать символ в ячейку, а также сдвинуть головку влево или вправо в соседнюю ячейку. Машина работает дискретно, по тактам и на каждом такте находится в одном из возможных состояний, которых конечное число. Для каждой пары (состояние, обозреваемый символ) определена тройка (записываемый символ, движение головки, новое состояние). До начала работы машина Тьюринга находится в начальном состоянии, а головка чтения-записи обозревает на ленте самую левую непустую ячейку. Таким образом, обозревая очередной символ, машина записывает новый символ (может быть, тот же самый), сдвигает головку влево, вправо или остается на месте и переходит в новое состояние или остается в прежнем.

Машина Тьюринга состоит из трех частей: ленты, считывающей (записывающей) головки и логического устройства (рис. 1).

Лента выступает в качестве внешней памяти. Она считается неограниченной (бесконечной). Уже это свидетельствует о том, что машина Тьюринга является модельным устройством, поскольку ни одно реальное устройство не может обладать памятью бесконечного размера.

Рис. 1 - Схема машина Тьюринга

Как и в машине Поста, лента разбита на отдельные ячейки, однако в машине Тьюринга неподвижной является головка, а лента передвигается относительно нее вправо или влево.

Другим отличием является то, что она работает не в двоичном, а некотором произвольном конечном алфавите A = {Δ, a1…an} – этот алфавит называется внешним. В нем выделяется специальный символ – Δ, называемый пустым знаком – его посылка в какую-либо ячейку стирает тот знак, который до этого там находился, и оставляет ячейку пустой. В каждую ячейку ленты может быть записан лишь один символ. Информация, хранящаяся на ленте, изображается конечной последовательностью знаков внешнего алфавита, отличных от пустого знака.

Головка всегда расположена над одной из ячеек ленты. Работа происходит тактами (шагами). Система исполняемых головкой команд предельно проста: на каждом такте она производит замену знака в обозреваемой ячейке ai знаком aj. При этом возможны сочетания:

−  j = i      – означает, что в обозреваемой ячейке знак не изменился;

−  i ≠ 0, j = 0 – хранившийся в ячейке знак заменяется пустым, т.е. стирается;

−  i = 0, j ≠ 0 – пустой знак заменяется непустым (с номером j в алфавите), т.е. производится вставка знака;

−  i ≠ j ≠ 0         – соответствует замене одного знака другим.

Таким образом, в машине Тьюринга реализуется система предельно простых команд обработки информации. Эта система команд обработки дополняется также предельно простой системой команд перемещений ленты: на ячейку влево, на ячейку вправо и остаться на месте, т.е. адрес обозреваемой ячейки в результате выполнения команды может либо измениться на 1, либо остаться неизменным. Однако, хотя фактически происходит перемещение ленты, обычно рассматривается сдвиг головки относительно обозреваемой секции. По этой причине команда сдвига ленты влево обозначается R (Right), сдвига вправо – L (Left), отсутствие сдвига – S (Stop). Мы будем говорить именно о сдвиге головки и считать R, L и S командами ее движения. Элементарность этих команд означает, что при необходимости обращения к содержимому некоторой ячейки, она отыскивается только посредством цепочки отдельных сдвигов на одну ячейку. Разумеется, это значительно удлиняет процесс обработки, зато позволяет обойтись без нумерации ячеек и использования команд перехода по адресу, т.е. сокращает количество истинно элементарных шагов, что важно в теоретическом отношении.

Обработка информации и выдача команд на запись знака, а также сдвига ленты в машине Тьюринга производится логическим устройством (ЛУ). ЛУ может находиться в одном из состояний, которые образуют конечное множество и обозначаются Q ={q1…qm, z} , причем состояние z соответствует завершению работы, а q1 является начальным (исходным). Q совместно со знаками R, L, S образуют внутренний алфавит машины. ЛУ имеет два входных канала (ai, qi) и три выходных (ai+1, qi+1, Di+1) (см. рис. 2):

Рис. 2 - Схема логического устройства машины Тьюринга

Понимать схему необходимо следующим образом: на такте i на один вход ЛУ подается знак из обозреваемой в данный момент ячейки (ai,), а на другой вход – знак, обозначающий состояние ЛУ в данный момент (qi). В зависимости от полученного сочетания знаков (ai, qi) и имеющихся правил обработки ЛУ вырабатывает и по первому выходному каналу направляет в обозреваемую ячейку новый знак (ai+1), подает команду перемещения головки (Di+1 из R, L и S), а также дает команду на вызов следующего управляющего знака (qi+1). Таким образом, элементарный шаг (такт) работы машины Тьюринга заключается в следующем: головка считывает символ из обозреваемой ячейки и, в зависимости от своего состояния и прочитанного символа, выполняет команду, в которой указано, какой символ записать (или стереть) и какое движение совершить. При этом и головка переходит в новое состояние. Схема функционирования такой машины представлена на рисунке 3.

Рис. 3 - Схема функционирования машины Тьюринга

алгоритмический машина пост тьюринг

В данной схеме отражено разделение памяти на внешнюю и внутреннюю. Внешняя представлена, как указывалось, в виде бесконечной ленты – она предназначена для хранения информации, закодированной в символах внешнего алфавита. Внутренняя память представлена двумя ячейками для хранения следующей команды в течение текущего такта: в Q передается из ЛУ и сохраняется следующее состояние (qi+1), а в D – команда сдвига (Di+1). Из Q по линии обратной связи qi+1 поступает в ЛУ, а из D команда поступает на исполнительный механизм, осуществляющий при необходимости перемещение ленты на одну позицию вправо или влево.

Общее правило, по которому работает машина Тьюринга, можно представить следующей записью: qi aj → qi’ aj’ Dk, т.е. после обзора символа aj головкой в состоянии qi в ячейку записывается символ aj’, головка переходит в состояние qi’, а лента совершает движение Dk. Для каждой комбинации qi aj имеется ровно одно правило преобразования (правил нет только для z, поскольку, попав в это состояние, машина останавливается). Это означает, что логический блок реализует функцию, сопоставляющую каждой паре входных сигналов qi aj одну и только одну тройку выходных qi’aj’Dk – она называется логической функцией машины и обычно представляется в виде таблицы (функциональной схемой машины), столбцы которой обозначаются символами состояний, а строки – знаками внешнего алфавита. Если знаков внешнего алфавита n, а число состояний ЛУ m, то, очевидно, общее число правил преобразования составит n×m.

Конкретная машина Тьюринга задается перечислением элементов множеств A и Q, а также логической функцией, которую реализует ЛУ, т.е. набором правил преобразования. Ясно, что различных множеств A, Q и логических функций может быть бесконечно много, т.е. и машин Тьюринга также бесконечно много.

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

Записать конфигурацию можно следующим образом: Δa1 qi aj…ak Δ, которая означает, что в слове из k символов обозревается секция номер j и при этом управляющее устройство находится в состоянии qi. Ясно, что конфигурация машины может содержать любое количество символов внешнего алфавита и лишь один символ внутреннего. Часто конфигурацию записывают в виде a1 qi a2, где a1 – слово на ленте слева от головки, a2 – слово на ленте справа от головки, включая обозреваемый знак. Слева от a1 и справа от a2 лента пуста.

Перед началом работы на пустую ленту записывается исходное слово a конечной длины в алфавите A; головка устанавливается над первым символом слова a, ЛУ переводится в состояние q1 (т.е. начальная конфигурация имеет вид q1a). Поскольку в каждой конфигурации реализуется только одно правило преобразования, начальная конфигурация однозначно определяет всю последующую работу машины, т.е. всю последовательность конфигураций вплоть до прекращения работы.

В зависимости от начальной конфигурации возможны два варианта развития событий:

1)  после конечного числа тактов машина останавливается по команде остановки; при этом на ленте оказывается конечная конфигурация, соответствующая выходной информации;

2)  остановки не происходит.

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

По своему устройству машина Тьюринга крайне примитивна. Она намного проще самых первых компьютеров. Примитивизм состоит в том, что у нее предельно прост набор элементарных операций, производимых головкой – считывание и запись, а также в том, что доступ к ячейкам памяти (секциям ленты) в ней происходит не по адресу, как в компьютерах, а путем последовательного перемещения вдоль ленты. По этой причине даже такие простые действия, как сложение или сравнение двух символов, машина Тьюринга производит за несколько шагов, а обычные операции сложения и умножения требуют весьма большого числа элементарных действий. Однако машина Тьюринга была придумана не как модель или прототип реальных вычислительных машин, а для того, чтобы показать принципиальную теоретическую возможность построения сколь угодно сложного алгоритма из предельно простых операций, причем сами операции и переход от одной к последующей машина выполняет автоматически.

Машина Тьюринга дает один из путей уточнения понятия алгоритма. В связи с этим возникают вопросы:

−  насколько общим является понятие машины Тьюринга?

−  можно ли считать, что способ задания алгоритмов с помощью машины Тьюринга является универсальным?

−  может ли всякий алгоритм задаваться таким образом?

На эти вопросы современная теория алгоритмов предлагает ответ в виде следующей гипотезы:

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

Эта гипотеза получила название тезиса Тьюринга. Как и тезис Черча, ее нельзя доказать, так как она связывает нестрогое определение понятия алгоритма со строгим определением машины Тьюринга.

В принципе, эта гипотеза может быть опровергнута, если удастся привести пример алгоритма, который не может быть реализован с помощью тьюринговой функциональной схемы. Однако все известные до сих пор алгоритмы могут быть заданы посредством тьюринговых функциональных схем.

 

5. Универсальная машина Тьюринга

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

Внешний алфавит информационных слов, с которыми оперирует машина Тьюринга, может быть произвольным, но конечным. Помимо него, необходим внутренний алфавит для обозначения внутренних состояний и некоторых особых ситуаций. В результате работа машины Тьюринга допускает символическое описание в виде специальной таблицы переходов. В каждой строке этой таблицы текущему входному символу и текущему состоянию ставится в соответствие выходной символ, новое состояние и указание, слева или справа от текущего нужно взять следующий обрабатываемый символ. Строки таблицы называются командами, а таблица в целом – программой. Работа машины Тьюринга начинается с «настройки» на начальное внутреннее состояние и первый символ входного слова. По ним в программе находится нужная команда, а в результате – выходной символ, новое состояние и место, откуда нужно считать следующий входной символ. Так происходит до тех пор, пока не будет достигнуто особое, «конечное» состояние, соответствующее решению задачи.

Основной результат идеи Тьюринга заключается не в том, что для любого алгоритма в интуитивном смысле может быть построена соответствующая машина, хотя этот факт и не вызывает сомнений в результате многочисленных проверок. С помощью результатов работы Тьюринга можно доказать, что машина не может решать задачи, которые интуитивно неразрешимы.

Неразрешимость таких задач на машине Тьюринга не есть следствие ее примитивности. Тьюринг, действительно, искал как можно более простую схему, позволяющую не только формализовать процесс решения, но и обладающую применимостью к любым задачам. Предположение Тьюринга о том, что всякий алгоритм может быть реализован соответствующей машиной, было всего лишь гипотезой. Однако весь последующий опыт позволил возвести этот тезис в ранг формального определения алгоритма. И, пожалуй, самым впечатляющим доказательством справедливости идеи Тьюринга явилось установление эквивалентности этого определения другими формальными определениями, данными независимо Э. Постом и русскими математиками А.А. Марковым и А.Н. Колмогоровым.

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

Работа машины происходит в нашем воображении. Следовательно, машины Тьюринга – вовсе не машины в обычном смысле, а скорее тексты на некотором языке, что вполне соответствует нашему интуитивному представлению об алгоритме.

Возникает вопрос, является ли алгоритмом работа любой машины Тьюринга? В их поведении есть много общего: все, что они «умеют», сводится к достаточно простым операциям поиска текущей команды, преобразования, входного символа в выходной, изменения внутреннего состояния и нахождения следующего входного символа. Эти операции носят настолько регулярный, «механический» характер, что их вполне можно описать в виде единственной программы для подходящей машины – универсальной машины Тьюринга.

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

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

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

В воображаемом устройстве универсальной машины использованы важные идеи, нашедшие позднее воплощение в особенностях конструкции и работы настоящих ЭВМ. В первую очередь, это работа по программе, представляющей собой символическую запись алгоритма на языке, «понятном» для исполнения не очень сложным устройством. Во-вторых, это наличие запоминающего устройства для хранения как исходной, промежуточной и конечной информации, так и самой программы. Память реальных ЭВМ всегда конечна, но это ограничение становится несущественным в современных ЭВМ, обладающих весьма большой памятью. Наконец, это возможность имитации работы любых специализированных устройств обработки информации на одной универсальной конструкции.

 

6. Нормальные алгоритмы Маркова

Кратко остановимся на третьем подходе к уточнению (конкретизации) понятия алгоритма. По смыслу оно близко к идеям Тьюринга, однако, в нем не используются представления о каких-либо машинах. Алгоритм задается системой подстановок, которые указывают, какие замены символов необходимо производить и в каком порядке эти подстановки должны следовать. Такой подход был предложен А.А. Марковым. В начале 50-х годов прошлого столетия было введено понятие нормального алгоритма (сам Марков называл их алгорифмами).

Вновь рассмотрим некоторый алфавит A, содержащий конечное число знаков (букв). Введем ряд определений:

Слово – это любая конечная последовательность знаков алфавита.

Число символов в слове называется его длиной.

Слово, длина которого равна нулю, называется пустым.

Слово s называется подсловом слова q, если q можно представить в виде q= rst, где r и t – любые слова в том же алфавите (в том числе и пустые).

Теперь можно определить понятие алгоритма (не являющееся строгим):

Алгоритмом в алфавите A называется эффективно вычислимая функция, областью определения которой служит какое-либо подмножество множества всех слов в алфавите A и значениями которой также являются слова в алфавите A.

В алгоритмах Маркова в качестве элементарного шага алгоритма принимается подстановка одного слова вместо другого. Пусть в алфавите A построено исходное слово P, которое содержит подслово Pr (в общем случае таких подслов в исходном слове может быть несколько), а также имеется некоторое слово Pk в том же алфавите.

Подстановкой называется замена первого по порядку подслова Pr исходного слова P на слово Pk. Обозначается подстановка Pr→Pk.

Алгоритм в данной форме представления задается системой подстановок, которая представляет собой последовательность (список) подстановок. Если в этом списке имеются подстановки с левыми частями, которые входят в P, то первая из них применяется к P, в результате чего оно переходит в другое слово P1. К нему вновь применяется схема подстановок и т.д. Процесс прекращается в двух случаях: либо в списке не нашлось подстановки с левой частью, входящей в Pn, либо при получении Pn была применена последняя подстановка.

Библиографический список

 

1.  Авдеев Р.Ф. Философия информационной цивилизации [Текст] / Р.Ф. Авдеев. – М.: ВЛАДОС, 2008.

2.  Булгаков И.С. Счетные машины [Текст] / И.С. Булгаков. – М.: Машгиз, 2010.

3.  Винер Н. Человек управляющий [Текст] / Н. Винер. – СПб.: Питер, 2009. – 288 с.

4.  Гутер Р.С. От абака до компьютера [Текст] / Р.С. Гутер, Ю.Л. Полунов. – М.: Знание, 2009.

5.  Ершов Ю.Л. Математическая логика [Текст] / Ю.Л. Ершов, Е.А. Палютин. – М.: Наука, 2008.

6.  Клини С. Введение в метаматематику [Текст] / С. Клини. – М.: Изд-во иностр. лит., 2008.

7.  Клини С. Машины Тьюринга и рекурсивные функции [Текст] / С. Клини. – М., 2010.

8.  Клини С. Математическая логика [Текст] / С. Клини. – М., 2009.

9.  Колин, К.К. Фундаментальные основы информатики: социальная информатика [Текст]: учеб. пособие для вузов / К.К. Колин. – М.: Академический Проект; Екатеринбург: Деловая книга, 2008.

10.  Кондаков Н.И. Логический словарь-справочник [Текст] / Н.И. Кондаков. – М.: Наука, 2010.

11.  Основы философии науки [Текст]: учеб. пособие для аспирантов / В.П. Кохановский [и др.]. – Ростов н/Д: Феникс, 2009.

12.  Ларичев О.И. Наука и искусство принятия решений [Текст] / О.И. Ларичев. – М.: Наука, 2009.

13.  Пенроуз Р. Новый ум короля: о компьютерах, мышлении и законах физики [Текст] / общ. ред. В.О. Малышенко; пер. с англ. – М.: Едиториал УРСС, 2008. – 384 с.

14.  Петров Ю.П. История и философия науки. Математика, вычислительная техника, информатика [Текст] / Ю.П. Петров. – СПб.: БХВ-Петербург, 2010.

15.  Поликарпов В.С. История науки и техники [Текст]: учеб. пособие / В.С. Поликарпов. – Ростов н/Д: Феникс, 2008.

16.  Рязанкин В.Н. Вычислительные клавишные машины [Текст] / В.Н. Рязанкин, Г.П. Евстигнеев, Н.Н. Тресвятский. – М.: Машгиз, 2009.

17.  Успенский В.А. Машина Поста [Текст] / В.А. Успенский. – М.: Наука, 2010. – 96 с.

18.  Успенский В.А. Теория алгоритмов: основные открытия и приложения [Текст] / В.А. Успенский, А.Л. Семенов. – М.: Наука, 2010. – 288 с.

19.  Чёрч А. Введение в математическую логику [Текст] / А. Чёрч. – М., 2008. Т.1.