8_1 (1019126)
Текст из файла
Какая именно команда программы будет выполняться в данный момент, определяется двумя параметрами: читаемым головкой символом и состоянием машины.
Результатами выполнения команды являются: новый символ записанный на ленту в ту ячейку, напротив которой находится в данный момент головка; перемещение головки на одну позицию (ячейку) вправо или влево вдоль ленты; переход машины в новое состояние. В частных случаях новый символ может быть равен старому, перемещение может отсутствовать, состояние может остаться прежним.
Формат команды имеет следующий вид:
a q b r D,
где а — читаемый символ; q — текущее состояние; b — символ записываемый в обозреваемую ячейку ленты вместо символа а; r — новое состояние; D — направление движения головки машины относительно ленты.
Символы выбираются из конечного алфавита А = {а1, . . . , a1}.
В дальнейшем будем использовать трехсимвольный алфавит {е 0, 1}, причем е будет означать «пустой (empty)» символ — отсутствие информации в ячейке, а с помощью нуля и единицы будут кодироваться все данные. Иногда используют двухсимвольный алфавит А = {е, 1}. В этом случае числа кодируются только единицами: нуль кодируется одной единицей, число один кодируется двумя единицами, а число х кодируется х + 1 единицами Это — единичная система счисления. Однако она плоха с точки зрения сложности задач (см. гл. 5).
Множество состояний обозначим Q= { q1, . . . , qk}. Направление движения D выбирается из множества {L, R, S} где L — движение влево, R — движение вправо, S — отсутствие лви жения.
Таким образом, команда 1 q3 0 q6 L означает: если, находясь в состоянии q3, машина Тьюринга обозревает ячейку ленты в которой записана 1, то машина должна записать в эту ячейку 0, произвести сдвиг головки относительно ленты влево на одну ячейку и перейти в состояние q6.
Это описание действия, соответствующего команде говорит о том, что команда может рассматриваться как отображение пар (a, q) в тройки (b, r, D), т. е. отображение
AxQ=> AxQx {L, R, S}.
Данное отображение является частичным, так как не для любой пары-аргумента существует тройка-результат. Но для произвольной пары существует не более одной тройки, т. е. отображение не является многозначным.
Все действия производятся в дискретном времени. Иначе говоря, можно рассматривать целочисленные моменты времени t = = 0, 1, 2, 3, ... Любое изменение происходит мгновенно в момент t = i и ничего не меняется между двумя соседними моментами времени.
Работает машина Тьюринга следующим образом. Стартовая конфигурация: на ленте находятся исходные данные — строка символов в алфавите А, состояние внутренней памяти соответствует некоторому оговоренному (всегда одному и тому же) начальному состоянию, например, q1. При этом головка машины обозревает некоторую ячейку ленты с записанным там символом а. Нормальным считается начальное положение головки напротив самого левого непустого символа, т. е. не совпадающего с е.
Момент старта рассматривается как нулевой момент времени. В момент старта выполняется первая команда, это единственная команда, начинающаяся с пары (a, q1). В результате выполнения команды машина перейдет в новое состояние, и головка машины прочтет новый символ с ленты. Эта пара (новый символ, новое состояние) станет начальной частью следующей команды и т. д. Машина будет продолжать работать в дискретном времени, шаг за шагом переходя из состояния в состояние, и постепенно изменяя содержимое ленты. Наконец, для некоторой пары (a, q) не окажется команды в программе. Такая ситуация считается завершающей. Машина прекращает функционирование. Оставшаяся запись на ленте считается записью результата.
Таким образом, машина Тьюринга реализует вычисление некоторой функции — отображения исходной строки символов в результирующую строку.
Существует несколько способов представления программы машины Тьюринга (множества команд). Два наиболее употребительных:
-
двумерная таблица (рис. 1.2);
-
диаграмма (нагруженный псевдограф).
В двумерной таблице строки помечаются различными символами алфавита, а столбцы — именами различных состояний машины, т. е. таблица имеет размер Ik. Каждой команде программы
Состояние Символ | q1 | … | q | … | qk |
a1 | |||||
… | |||||
brD | |||||
… | |||||
a1 |
Рис. 1.2. Табличная форма программы машины Тьюринга
соответствует единственная клетка в таблице. Она определяется для команды aqbrD следующим образом: в клетку, находящуюся на пересечении строки, помеченной символом я, и столбца помеченного состоянием q. вписывается тройка b r D.
Для некоторых пар (а, q) в программе нет команд, следовательно, соответствующие клетки таблицы остаются пустыми. При достижении в процессе работы пустой клетки машина Тьюринга останавливается.
В качестве простого примера приведем программу вычисления функции S(x) = x + 1, т. е. увеличение аргумента на единицу (рис. 1.3). Используем алфавит A = {e, 0, 1}, причем x будем кодировать последовательностью нулей и единиц так. как это принято при двоичном кодировании целых неотрицательных чисел.
предположим также, что в момент старта головка машины Тьюринга находится напротив крайней левой ячейки с символом 1.
q1 | q2 | q3 | q4 | |
0 | 0q1R | 1q3L | 0q3L | |
1 | 1q1R | 0q2L | 1q3L | |
e | eq2L | 1q4S | eq4R |
Р и с. 1.3. Программа машины Тьюринга для вычисления функции S(x)=x+1
Первая выполняемая команда —1q11q1R оставляет 1 в ячейке ленты, оставляет неизменным состояние q1 и производит сдвиг головки вправо по ленте. В новой читаемой ячейке может оказаться любой из трех символов алфавита. Если это 0 или 1, то производится дальнейшее движение вправо до окончания кода числа х. Если же встретится символ е, то это будет означать, что код числа закончился и головка находится справа от младшей цифры кода числа. После этого, собственно, и начинается процесс прибавления единицы. Если младшая цифра — 0 то достаточно заменить се на 1 (команда 0 q2 1 q3 L) и начать обратное движение к исходной позиции. Если младшая цифра — 1 то результатом в данной ячейке будет 0 (сложение по mod 2), и единица перейдет в следующий по старшинству разряд (влево). Процесс распространения переноса может закончиться где-то внутри кода числа и тогда необходимо осуществить «прокрутку» ленты так, чтобы машина остановилась на крайней левой единице кода результата (x+1)
Второй пример - программа вычисления функции Z(x) = 0(x) = 0, превращающей запись любого аргумента. x в запись нуля (рис. 1.4). Эта программа стирает с ленты код x, т. е. запол
q1 | q2 | |
0 | eq1R | |
1 | eq1R | |
е | 0q2R |
P 11 с. 1.4. Программа машины Тьюринга для вычисления функции 0(x) = 0
няет клетки символом е и перед остановкой записывает в текущую клетку 0.
Более длинная программа получается для вычисления функции Inm (x1,x2, … , xn) выбирающей m-й аргумент из последовательности п аргументов, 1 m n, Inm (х1, х2, ... ,xn)=xm (рис. 1.5).
Представление последовательности п аргументов зададим на ленте в виде записанных один за другим через разделитель — пустую клетку е — двоичных кодов хi. Программа, написанная для конкретного значения т, действует следующим образом. Сначала стирается (заменяется на е ...е) первый аргумент, затем стирается второй, ..., стирается (т - 1)-й; затем подтверждается т-й аргумент; затем стираются оставшиеся аргументы.
q1 | q2 | … | qm-1 | qm | qm+1 | … | qn | qn+1 | |
0 | eq1R | eq2R | … | eqm-1R | 0qmR | eqm+1R | eqnR | ||
1 | eq1R | eq2R | … | eqm-1R | 1qmR | eqm+1R | eqnR | ||
е | eq2R | eq3R | … | eqmR | eqm+1R | eqm+2R | eqn+1R |
Рис. 1.5. Программа машины Тьюринга для вычисления функции
Inm(x1, x2, … , xn)
Другой способ представления программы машины Тьюринга — диаграмма (рис. 1.6).
Диаграмма представляет собой геометрический объект, состоящий из вершин (обозначаемых точками или окружностями) и дуг (рисуемых в виде направленных отрезков прямой со стрелкой на одном из концов или в виде отрезков несамопсресекаю-щихся кривых). Каждой вершине приписывается состояние машины Тьюринга: таким образом вершин в диаграмме ровно столько, сколько имеется состояний. Дуге, соединяющей две вершины qi и qj, приписывается некоторый символ а алфавита А и двойка b D так, что запись a qi b qj D образует команду программы машины Тьюринга.
Дуга (стрелка) символизирует переход из состояния qi в состояние qj при условии, что головка читает символ а. Одновременно с этим символ а заменяется на символ b и совершается движение D. По этой причине диаграмму называют диаграммой (графом) переходов.
Рис. 1.6. Элемент диаграммы. Рис. 1.7. Диаграмма машины
Характеристики
Тип файла документ
Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.
Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.
Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.