Как сделать транспозицию в машине тьюринга
Добавил пользователь Skiper Обновлено: 05.10.2024
Машина Тьюринга состоит из трех частей: ленты, считывающе-записывающей головки и логического устройства (рис. 2.6).
Лента выступает в качестве внешней памяти; она считается неограниченной (бесконечной) - уже это свидетельствует о том, что машина Тьюринга является модельным устройством, поскольку ни одно реальное устройство не может обладать памятью бесконечного размера.
Рис. 2.6. Схема машины Тьюринга
Как и в машине Поста, лента разбита на отдельные ячейки, однако, в машине Тьюринга неподвижной является головка, а лента передвигается относительно нее вправо или влево. Другим отличием является то, что она работает не в двоичном, а некотором произвольном конечном алфавите А = а1. ап> - этот алфавит называется внешним. В нем выделяется специальный символ - ∆, называемый пустым знаком - его посылка в какую-либо ячейку стирает тот знак, который до этого там находился, и оставляет ячейку пустой. В каждую ячейку ленты может быть записан лишь один символ. Информация, хранящаяся на ленте, изображается конечной последовательностью знаков внешнего алфавита, отличных от пустого знака.
Головка всегда расположена над одной из ячеек ленты. Работа происходит тактами (шагами). Система исполняемых головкой команд предельно проста: на каждом такте она производит замену знака в обозреваемой ячейке ai знаком aj. При этом возможны сочетания:
- j =i— это означает, что в обозреваемой ячейке знак не изменился;
- i ≠ 0, j = 0 означает, что хранившийся в ячейке знак заменяется пустым, т.е. стирается;
- i = 0, j ≠ 0 означает, что пустой знак заменяется непустым (с номером j в алфавите), т.е. производится вставка знака;
- i ≠ j ≠ 0 соответствует замене одного знака другим.
Обработка информации и выдача команд на запись знака, а также сдвига ленты в машине Тьюринга производится логическим устройством (ЛУ). Оно может находиться в одном из состояний, которые образуют конечное множество и обозначаются Q = q1…qm, z>, причем, состояние z соответствует завершению работы, a q1 является начальным (исходным). Q совместно со знаками R, L, S образуют внутренний алфавит машины. ЛУ имеет два входных канала (ai, qi) и три выходных (аi+1, qi+1, Di+1) (см. рис. 2.7):
Рис. 2.7. Изображение логического устройства
Понимать схему необходимо следующим образом: на такте i на один вход ЛУ подается знак из обозреваемой в данный момент ячейки (ai), а на другой вход - знак, обозначающий состояние ЛУ в данный момент (qi). В зависимости от полученного сочетания знаков (ai, qi) и имеющихся правил обработки ЛУ вырабатывает и по первому выходному каналу направляет в обозреваемую ячейку новый знак (ai+1), подает команду перемещения головки (Di+1 из R, L и S), а также дает команду на вызов следующего управляющего знака (qi+1). Таким образом, элементарный шаг (такт) работы машины Тьюринга заключается в следующем: головка считывает символ из обозреваемой ячейки и, в зависимости от своего состояния и прочитанного символа, выполняет команду, в которой указано, какой символ записать (или стереть) и какое движение совершить. При этом и головка переходит в новое состояние. Схема функционирования такой машины представлена на рис. 2.8.
Рис. 2.8. Схема функционирования машины Тьюринга
В данной схеме отражено разделение памяти на внешнюю и внутреннюю. Внешняя представлена, как указывалось, в виде бесконечной ленты - она предназначена для хранения информации, закодированной в символах внешнего алфавита. Внутренняя память представлена двумя ячейками для хранения следующей команды в течение текущего такта: в Q передается из ЛУ и сохраняется следующее состояние (qi+1), а в D - команда сдвига (Di+1). Из Q по линии обратной связи qi+1 поступает в ЛУ, а из D команда поступает на исполнительный механизм, осуществляющий при необходимости перемещение ленты на одну позицию вправо или влево.
Общее правило, по которому работает машина Тьюринга, можно представить следующей записью: qiaj→qi'aj'Dk, т.е. после обзора символа aj головкой в состоянии ai, в ячейку записывается символ aj', головка переходит в состояние qi', а лента совершает движение Dk. Для каждой комбинации qiaj имеется роено одно правило преобразования (правил нет только для z, поскольку, попав в это состояние, машина останавливается). Это означает, что логический блок реализует функцию, сопоставляющую каждой паре входных сигналов qiaj одну и только одну тройку выходных qi'aj'Dk - она называется логической функцией машины и обычно представляется в виде таблицы (функциональной схемой машины), столбцы которой обозначаются символами состояний, а строки - знаками внешнего алфавита. Если знаков внешнего алфавита п, а число состояний ЛУ т, то, очевидно, общее число правил преобразования составит п∙т.
Конкретная машина Тьюринга задается перечислением элементов множеств А и Q, а также, логической функцией, которую реализует ЛУ, т.е. набором правил преобразования. Ясно, что различных множеств A, Q и логических функций может быть бесконечно много, т.е. и машин Тьюринга также бесконечно много.
Совокупность состояний всех ячеек ленты, состояния ЛУ и положение головки называется конфигурацией машины.
Записать конфигурацию можно следующим образом: ∆а1qiaj. аk∆ которая означает, что в слове из k символов обозревается секция номер j и при этом управляющее устройство находится в состоянии qi. Ясно, что конфигурация машины может содержать любое количество символов внешнего алфавита и лишь один символ внутреннего. Часто конфигурацию записывают в виде α1qiα2, где α1 - слово на ленте слева от головки, α2 - слово на ленте справа от головки, включая обозреваемый знак. Слева от α1 и справа от α2 лента пуста. Конфигурация, изображенная на рис. 2.6., может быть записана следующим образом: а1∆а2∆qa3а4аk, на рис. 2.8.- 1q1111.
Перед началом работы на пустую ленту записывается исходное слово α конечной длины в алфавите А; головка устанавливается над первым символом слова α, ЛУ переводится в состояние q1 (т.е. начальная конфигурация имеет вид q1α). Поскольку в каждой конфигурации реализуется только одно правило преобразования, начальная конфигурация однозначно определяет всю последующую работу машины, т.е. всю последовательность конфигураций вплоть до прекращения работы.
В зависимости от начальной конфигурации возможны два варианта развития событий:
- После конечного числа тактов машина останавливается по команде остановки; при этом на ленте оказывается конечная конфигурация, соответствующая выходной информации;
- Остановки не происходит.
В первом случае говорят, что данная машина применима к начальной информации, во втором - нет. Вся совокупность входных конфигураций, при которых машина обеспечивает получение результата, образуют класс решаемых задач. Очевидно, применять машину Тьюринга для задачи, не входящей в класс решаемых, бессмысленно. С другой стороны, во многих случаях возможно расширение класса решаемых задач за счет создания другой машины Тьюринга. Возникает вопрос: можно ли построить такую универсальную машину (хотя бы на теоретическом уровне), которая решала бы любую задачу?
Рассмотрим решение задачи о добавлении 1 к унарному числу посредством машины Тьюринга. Внешний алфавит может быть задан множеством А = , где 1 соответствует заполненной секции, а ∆ - пустому знаку, причем заполненные следуют друг за другом подряд. Внутренний алфавит задается множеством Q = q, z>, где q соответствует рабочему состоянию ЛУ, a z-остановке. Набор всех правил преобразования (логическая функция) может быть представлен функциональной схемой:
Рис. 2.9. Логическая функция
Составляется функциональная схема в виде таблицы таким образом, что знаки, обозначающие колонки и строки, определяют входные параметры ЛУ, а в ячейке таблицы на их пересечении стоит выходная команда. В частности, если головка машины обозревает секцию ленты со знаком 1 и машина находится в рабочем состоянии (q), то результатом ее работе на данном такте должно стать повторение 1 в данной секции и переход на одну секцию вправо R (при этом, как указывалось, лента сдвигается влево) - эта команда записывается как q1R. Если же в обозреваемой секции ∆, а состояние ЛУ q, то ∆ будет заменен 1, сдвига ленты производиться не будет и машина остановится – z1S. При комбинации на входе ∆z, как и 1z, машина находится в нерабочем состоянии - не происходит ни изменения конфигурации, ни движения - по этой причине такие комбинации в функциональных схемах в дальнейшем отображаться не будут.
Пусть начальной является конфигурация 1q1111*. Тогда работа машины в соответствии с описанной логической функции будет происходить следующим образом:
Такт 1 Обозревается 1, в ЛУ состояние q. Выходная команда q1R, что эквивалентно перемещению головки по отношению ленты на 1 шаг вправо. Следовательно, образуется промежуточная конфигурация 11 q111.
Такт 2 - аналогичным образом осуществляется переход к конфигурации 111q11.
Такт 3 - переход к конфигурации 1111q1.
Такт 4 - переход к конфигурации 11111q∆ (здесь для лучшего понимания правый ∆ указан в явном виде).
Такт 5 Обозревается ∆, в ЛУ состояние q. Выходная команда z1S - вместо ∆ в ячейку записывается 1, сдвига нет, работа прекращается. Конечная конфигурация 111111z.
* Как указывалось выше, незначащие пустые секции слева и справа от заполненных в конфигурацию не включаются; поскольку в данной задаче несколько заполненных секций следуют подряд, только они и указываются в конфигурации.
Имеется запись многоразрядного целого числа п в десятичной системе счисления; построить машину Тьюринга, которая обеспечивала бы вычисление значение n + 1.
Используем внешний алфавит А = , в котором символ ∆ соответствует пустому знаку. Внутренний алфавит, как и в предыдущей задаче, образуется двумя состояниями - рабочим (q) и остановкой (z) (Q = q, z>). Исходное число п, а также результат - п + 1 - записываются в десятичной системе, причем, цифры размещаются по одной в соседних ячейках без пропусков. Функциональную схему представляется таблицей (для удобства строка будут соответствовать состоянию q, а столбцы - знакам внешнего алфавита):
Рис. 2.10. Функциональная схема
Пусть начальной конфигурацией будет 21 q9.
Такт 1 q9→q0L, т.е. 9 будет заменена на 0 и головка сдвинется на разряд десятков - промежуточная конфигурация 2q10.
Такт 2 q1→z2S, т.е. 1 будет заменена на 2 и произойдет остановка с конечной конфигурацией 2z20, т.е. получен результат сложения 219 + 1.
Пусть начальной будет конфигурация 99q9.
Такт 1 q9→q0L, т.е. сформируется промежуточная конфигурация 9q90.
Такт 2 q9→ q0L - возникнет конфигурация q900.
Такт 3 q9→q0L - возникнет q∆000.
Такт 4 q∆→z1S - возникнет z1000 и работа прекращается.
Таким образом, описанный алгоритм действительно обеспечивает суммирование любого целого десятичного числа и единицы. Ясно также, что при необходимости произвести сложение не с единицей, а с каким-то целым т, то данный алгоритм необходимо повторить т раз. Умножение целых чисел также может быть сведено к сложению числа с самим собой. Следовательно, машины Тьюринга обладают важным свойством - возможностью построения новой машины путем объединения уже имеющихся - такая операция называется композицией.
По своему устройству машина Тьюринга крайне примитивна. Она намного проще самых первых компьютеров. Примитивизм состоит в том, что у нее предельно прост набор элементарных операций, производимых головкой - считывание и запись, а также в том, что доступ к ячейкам памяти (секциям ленты) в ней происходит не по адресу, как в компьютерах, а путем последовательного перемещения вдоль ленты. По этой причине даже такие простые действия как сложение или сравнение двух символов машина Тьюринга производит за несколько шагов, а обычные операции сложения и умножения требуют весьма большого числа элементарных действий. Однако машина Тьюринга была придумана не как модель (прототип) реальных вычислительных машин, а для того, чтобы показать принципиальную (теоретическую) возможность построения сколь угодно сложного алгоритма из предельно простых операций, причем сами операции и переход от одной к последующей машина выполняет автоматически.
Всякий алгоритм может быть задан посредством тьюринговой функциональной схемы и реализован в соответствующей машине Тьюринга.
Эта гипотеза получила название тезиса Тьюринга. Как и тезис Черча, ее нельзя доказать, так как она связывает нестрогое определение понятия алгоритма со строгим определением машины Тьюринга.
В принципе, эта гипотеза может быть опровергнута, если удастся привести пример алгоритма, который не может быть реализован с помощью тьюринговой функциональной схемы. Однако все известные до сих пор алгоритмы могут быть заданы посредством тьюринговых функциональных схем.
Машина Тьюринга - это универсальная учебная машина, созданная для уточнения понятия алгоритм.
Структура машины Тьюринга
Машина Тьюринга состоит из:
- бесконечной в обе стороны ленты, разделенной на ячейки;
- каретки (читающей и записывающей головки);
- программируемого автомата.
Программируемый автомат управляет кареткой, посылая ей команды в соответствии с заложенной в него сменяемой программой. Лента выполняет роль внешней памяти компьютера, автомат — роль процессора, а каретка служит для ввода и вывода данных.
Программа для машины Тьюринга
Программы для машин Тьюринга записываются в виде таблицы, где первые столбец и строка содержат буквы внешнего алфавита и возможные внутренние состояния автомата (внутренний алфавит). Содержимое таблицы представляет собой команды для машины Тьюринга. Буква, которую считывает головка в ячейке (над которой она находится в данный момент), и внутренне состояние головки определяют, какую команду нужно выполнить. Команда определяется пересечением символов внешнего и внутреннего алфавитов в таблице.
Чтобы задать конкретную машину Тьюринга, требуется описать для нее следующие составляющие:
Внешний алфавит. Конечное множество (обозначают буквой А), элементы которого называются буквами (символами). Одна из букв этого алфавита (например, а0) должна представлять собой пустой символ.
Например, алфавит машины Тьюринга, работающей с двоичными числами, задается в виде A = .
Непрерывную цепочку символов на ленте называют словом.
Автоматом называют устройство, работающее без участия человека. Автомат в машине Тьюринга имеет несколько состояний и при определенных условиях переходит из одного состояния в другое. Множество состояний автомата называют внутренним алфавитом.
Внутренний алфавит. Конечное множество состояний каретки (автомата). Обозначается буквой Q=. Одно из состояний - q1- должно быть начальным (запускающим программу). Еще одно из состояний (q0) должно быть конечным (завершающим программу) – состояние остановка.
Таблица переходов. Описание поведения автомата (каретки) в зависимости от состояния и считанного символа.
Автомат машины Тьюринга в процессе своей работы управляется программой, во время каждого шага которой выполняются последовательно следующие действия:
- Записывать символ внешнего алфавита в ячейку (в том числе и пустой), заменяя находившийся в ней (в том числе и пустой).
- Передвигаться на одну ячейку влево или вправо.
- Менять свое внутреннее состояние.
Поэтому при составлении программы для каждой пары (символ, состояние) нужно определить три параметра: символ ai из выбранного алфавита A, направление перемещения каретки ("←” — влево, "→” — вправо, "точка” — нет перемещения) и новое состояние автомата qk.
Например, команда 1 "←” q2 обозначает "заменить символ на 1, переместить каретку влево на одну ячейку и перейти в состояние q2”.
Предполагается, что универсальный исполнитель должен уметь доказывать существование или отсутствие алгоритма для той или иной задачи.
Тезис Чёрча-Тьюринга:
| Любой алгоритм может быть представлен как программа для машины Тьюринга. Алгоритм - это программа для машины Тьюринга |
Т.о. можно дать формальное определение алгоритма по Тьюрингу. Машина Тьюринга - математический объект, и данное на ее основе определение алгоритма может использоваться для доказательства.
Примеры работы машины Тьюринга
Задача 1. 1
На ленте записано число в двоичной системе счисления. Каретка находится где-то над числом. Требуется увеличить число на единицу.
Чтобы решить задачу, нам нужно:
-определить алфавит машины Тьюринга А,
- определить набор состояний Q,
- составить программу (т.е. для каждой пары (аi,qi) определить команду автомата.)
Алфавит машины Тьюринга, работающей с двоичными цифрами будет включать цифры 0, 1 и пробел a0. Т.е. А=.
Определим возможные состояния:
1. q1 - автомат ищет правый конец слова (числа) на ленте
2. q2 - автомат увеличивает число на 1, проходя его слева направо и останавливается, закончив работу.
Напишем программу:
1 часть. q1 - автомат ищет правый конец слова (числа на ленте)
1)если в рабочей ячейке записано 0 - переместиться вправо
2)если в рабочей ячейке записано 1 - переместиться вправо
3) если в рабочей ячейке пробел, переместить каретку влево и перейти в состояние q2
Составим таблицу переходов для q1 т.о.:
| q1 | |
| 0 | 0 → q1 |
| 1 | 1 → q1 |
| a0 | a0 ← q2 |
1) если в рабочей ячейке записана цифра 0, записать в нее 1 и стоп
2) если в рабочей ячейке записана цифра 1, выполнить перенос в старший разряд — записать в ячейку 0 и переместиться влево.
3) если в рабочей ячейке пробел, записать в нее 1 и стоп.
Добавим в нашу таблицу состояние q2:
| алф\состояния | q1 | q2 |
| 0 | 0 → q1 | 1 . q0 |
| 1 | 1 → q1 | 0 ← |
| a0 | a0 ← q2 | 1 . q0 |
Примечание: длина слова и последовательность символов значения не имеют. На рисунке приводится пример последовательности выполнения команд для конкретного случая. Если на ленте будет другое слово, то и последовательность выполнения команд будет другой. Несмотря на это, данная программа для машины Тьюринга (на рисунке – таблица слева) применима к любым словам описанного внешнего алфавита (соблюдается свойство применимости алгоритма ко всем однотипным задачам – массовость).
Вопросы: 1
1. Что такое универсальный исполнитель?
2. Опишите устройство и систему программирования машины Тьюринга.
3. Что такое состояние машины Тьюринга?
4. Сопоставьте устройство машины Тьюринга с устройством компьютера. Какие устройства машины Тьюринга выполняют те же функции, что и аналогичные устройства компьютера?
5. В чем особенность состояний q0 и q1 машины Тьюринга?
6. По какому принципу можно построить программу для машины Тьюринга, которая последовательно выполняет операции А и Б?
7. Сформулируйте тезис Чёрча — Тьюринга.
Компьютерный практикум:
1. Дано целое число в троичной системе счисления; нужно увеличить его на единицу. Для реализации программы использовать учебную модель машины Тьюринга.
2. К данному троичному числу прибавить 2.
3. Прибавление единицы для целых чисел в пятеричной системе счисления
4. Составьте два варианта программы для машины Тьюринга, решающей следующую задачу: целое десятичное число нужно умножить на 10. Головка автомата расположена: а) левее числа на какой-то свободной ячейке; б) правее числа на какой-то свободной ячейке.
5. На ленте машины Тьюринга слева от головки автомата расположена группа подряд стоящих звездочек. Нужно стереть все звездочки и получить на ленте число, равное первоначальному количеству звездочек. Составить программу, реализовать ее на учебной модели машины Тьюринга. Протестировать программу.
Машина Тьюринга программа (К. Поляков)
Дополнительный материал:
4. Пильщиков В.Н., Абрамов В.Г., Вылиток А.А., Горячая И.В. Машины Тьюринга и алгоритмы Маркова. Решение задач. М.: МГУ, 2006.
Использованная литература:
1. К.Ю. Поляков, Е.А. Еремин "Элементы теории алгоритмов". Журнал "Информатика" №1, 2012 г.
Данные материалы полезны при первоначальном знакомстве с понятием машины Тьюринга. Теоретический материал изложен очень лаконично и поэтому будет понятен любому человеку, желающему расширить свой кругозор. Тема раскрывается посредством многообразия примеров и задач со схематическим изображением.
Машина Тьюрингапредставляет собой гипотетический аппарат преобразования слов. Под словом понимается произвольная последовательность символов, входящих в алфавит символов (обычно это или цифры, или начальные буквы латинского алфавита).
В состав машины Тьюринга входят: 1) бесконечная лента, разделенная на ячейки, на которой записано слово; 2) управляющее устройство, которое осуществляет преобразование слова.
В каждой ячейке записывается один символ слова. Выделяется особый пустой символ. Он заполняет все ячейки слева и справа от слова. Один из символов ленты является текущим, или, говорят, что на него указывает головка. Текущий символ можно выделять цветом или указывать на него стрелкой.
c
a
Управляющее устройство характеризуется алфавитом символов, из которых может состоять слово, и множеством состояний, в котором оно может находиться. Считается, что в алфавите символов всегда присутствует пустой символ.
Работа управляющего устройства состоит из последовательно выполняющихся тактов.
Каждый такт работы состоит в следующем: 1) чтение текущего символа ленты; 2) запись на его место нового (или, в частном случае, того же самого) символа; 3) смещение головки на одну ячейку влево, вправо или отсутствие смещения; 4) переход в новое состояние (возможно, совпадающее с текущим) или происходит останов (завершение работы).
Характеристики управляющего устройства удобно записывать в виде таблицы, в которой по строкам записываются состояния, а по столбцам символы. При этом используются следующие обозначения: R- смещение головки вправо, L- смещение головки влево, N- отсутствие смещения, ! – останов (т.е. завершение работы), q1, q2, … - состояния, ƛ – пустой символ
Пример Машины Тьюринга. Алфавит символов состоит из . Количество состояний – 2.
Сертификат и скидка на обучение каждому участнику
Написать программу на машине Тьюринга, прибавляющую число 2 к введенному числу.
Написать на машине Тьюринга программу, прибавляющую 3 к введенному числу.
Перенести первый символ непустого слова P в его конец. Алфавит : A=.
Если первый символ – это a, то надо перейти в состояние q2, в котором автомат бежит вправо и записывает в конце a. Если же первым был символ b, тогда надо перейти в состояние q3, где делается всё то же самое, только в конце записывается символ b. Если же первым был символ c, тогда переходим в состояние q4, в котором автомат дописывает за входным словом символ c.
Если первый и последний символы (непустого) слова P одинаковы, тогда это слово не менять, а иначе заменить его пустым словом. Алфавит: A =< a , b , c >.
Для решения этой задачи предлагается выполнить следующие действия:
Запомнить первый символ входного слова, не стирая его (перейти в состояние q 1 , если первый символ – a , q 3 , если первый символ – b и q 5 , если первый символ – c ).
Переместить автомат под последний символ и сравнить его с запомненным (в q 2 для a , в q 4 для b и в q 6 для c ). Если они равны, то больше ничего не делать.
В противном случае уничтожить всё входное слово ( q 7 ).
Удалить из слова P его второй символ, если такой есть. Алфавит: A =< a , b >.
Запомнить первый символ, стереть второй символ и установить на его месте первый.
Удалить из слова P первое вхождение символа a , если такое есть. Алфавит : A=.
Если первый символ слова – a , то стереть его и остановиться. Иначе сдвигаем символы слова на один символ вправо до тех пор, пока не найдем символ a .
Сдвиг символов осуществляется так: в очередной клетке записываем b (если в q 1 ) или c (если в q 2 ), переходим вправо и меняем состояние на q 1 (если в текущей клетке было записано b ) или на q 2 (если было записано c ), где осуществляется дальнейшая запись. Если в очередной клетке записано a или пробел, то записываем в нее запомненный символ и останавливаем программу.
Если P - непустое слово, то за его первым символом вставить символ a . Алфавит: A = < a , b , c >.
Аналогично заданию 5 запоминаем первый символ слова, меняем его на символ a , переходим на одну клетку влево и ставим там этот символ.
Вставить в слово P символ a за первым символом c , если такое есть. Алфавит: A = < a , b , c >.
Просматриваем слово до символа c или пустой клетки (в последнем случае останавливаем программу сразу). Затем, если c найден, запоминаем его и меняем на символ a , а далее запускаем цикл, который справа налево сдвигает символы слова, первоначально вставляя символ c перед a .
Удалить из P все вхождения символа a . A = < a , b , c >.
Вместо сдвига символов слова для закрытия образующихся дырок можно построить новое слово справа от предыдущего. Чтобы разграничить эти слова, отделим их некоторым вспомогательным символом, например знаком = , отличным от всех символов алфавита A .
Идем в конец слова и ставим знак = .
После этого возвращаемся к началу входного слова.
Этот цикл завершается, когда при возврате налево мы увидим в качестве первого символа знак = . Это признак того, что мы полностью просмотрели входное слово и перенесли все его символы, отличные от a , в формируемое справа выходное слово. Надо этот знак стереть, сдвинуться вправо под выходное слово и остановиться.
Удвоить слово P , поставив между ним и его копией знак = . Алфавит: A = < a , b >.
Вначале записываем знак = за входным словом. Затем возвращаемся под первый символ входного слова.
Когда мы скопируем последний символ входного слова и вернёмся к его двойнику, то затем после сдвига на одну позицию вправо мы попадём на знак = . Это сигнал о том, что входное слово полностью скопировано, поэтому останавливаем программу.
Читайте также: