Введение
Машина Тьюринга - это очень простое вычислительное
устройство. Она состоит из ленты бесконечной
длины, разделенной на ячейки, и головки,
которая перемещается вдоль ленты и способна
читать и записывать символы. Также у машины
Тьюринга есть такая характеристика, как
состояние, которое может выражаться целым
числом от нуля до некоторой максимальной
величины. В зависимости от состояния
машина Тьюринга может выполнить одно
из трех действий: записать символ в ячейку,
передвинуться на одну ячейку вправо или
влево и установить внутреннее состояние.
Устройство машины Тьюринга чрезвычайно
просто, однако на ней можно выполнить
практически любую программу. Для выполнения
всех этих действий предусмотрена специальная
таблица правил, в которой прописано, что
нужно делать при различных комбинациях
текущих состояний и символов, прочитанных
с ленты. В 1947 г. Алан Тьюринг расширил
определение, описав "универсальную
машину Тьюринга". Позже для решения
определенных классов задач была введена
ее разновидность, которая позволяла выполнять
не одну задачу, а несколько
Содержание
- Устройство машины Тьюринга
- Описание машины Тьюринга
- Пример машины Тьюринга
- Варианты машины Тьюринга
- Машина Тьюринга,работающая на бесконечной ленте
- Двумерные машины Тьюринга
- Список использованной литературы
Устройство машины Тьюринга
В состав машины Тьюринга входит бесконечная
,в обе стороны лента (бывают машины
, которые имеют несколько бесконечных
лент), разделённая на ячейки и управляющее
устройство, которое может находиться
в одном из множества состояний. Число
возможных состояний этого устройства
конечно и точно задано.
Управляющее устройство может перемещаться
влево и вправо по ленте, читать и записывать
в ячейки ленты символы некоторого конечного
алфавита. Выделяется особый пустой символ,
заполняющий все клетки ленты, кроме тех
из них , на которых записаны входные данные.
Управляющее устройство работает согласно
правилам перехода, которые представляют
алгоритм, реализуемый данной машиной
Тьюринга. Каждое правило перехода предписывает
машине, в зависимости от текущего состояния
и наблюдаемого в текущей клетке символа,
записать в эту клетку новый символ, перейти
в новое состояние и переместиться на
одну клетку влево или вправо. Некоторые
состояния машины Тьюринга могут быть
помечены как терминальные, и переход
в любое из них означает конец работы,
остановку алгоритма.
Машина Тьюринга называется детерминированной, если каждой
комбинации состояния и ленточного символа
в таблице соответствует не более одного
правила. Если существует пара «ленточный
символ — состояние», для которой существует
2 и более команд, такая машина Тьюринга называется недетерминированной
Описание машины
Тьюринга
Алан Тьюринг (Turing) в 1936 году
опубликовал в трудах Лондонского математического
общества статью "О вычислимых числах
в приложении к проблеме разрешения",
которая наравне с работами Поста и Черча
лежит в основе современной теории алгоритмов.
Предыстория
создания этой работы связана с формулировкой
Давидом Гильбертом на Международном
математическом конгрессе в Париже в 1900
году неразрешенных математических проблем.
Одной из них была задача доказательства
непротиворечивости системы аксиом обычной
арифметики, которую Гильберт в дальнейшем
уточнил как "проблему разрешимости"
- нахождение общего метода, для определения
выполнимости данного высказывания на
языке формальной логики.
Статья
Тьюринга как раз и давала ответ на эту
проблему - вторая проблема Гильберта
оказалась неразрешимой. Но значение статьи
Тьюринга выходило далеко за рамки той
задачи, по поводу которой она была написана.
Приведем
характеристику этой работы, принадлежащую
Джону Хопкрофту: "Работая над проблемой
Гильберта, Тьюрингу пришлось дать четкое
определение самого понятия метода. Отталкиваясь
от интуитивного представления о методе
как о некоем алгоритме, т.е. процедуре,
которая может быть выполнена механически,
без творческого вмешательства, он показал,
как эту идею можно воплотить в виде подробной
модели вычислительного процесса. Полученная
модель вычислений, в которой каждый алгоритм
разбивался на последовательность простых,
элементарных шагов, и была логической
конструкцией, названной впоследствии
машиной Тьюринга".
Машина
Тьюринга является расширением модели
конечного автомата, расширением, включающим
потенциально бесконечную память с возможностью
перехода (движения) от обозреваемой в
данный момент ячейки к ее левому или правому
соседу.
Формально
машина Тьюринга может быть описана следующим
образом. Пусть заданы:
конечное
множество состояний – Q, в которых может
находиться машина Тьюринга;
конечное
множество символов ленты – Г;
функция
δ (функция переходов или программа), которая
задается отображением пары из декартова
произведения Q x Г (машина находится в
состоянии qi и обозревает символ gi) в тройку
декартова произведения Q х Г х {L,R} (машина
переходит в состояние qi, заменяет символ
gi на символ gj и передвигается влево или
вправо на один символ ленты) – Q x Г-->Q
х Г х {L,R}
один
символ из Г-->е (пустой);
подмножество
Σ є Г - -> определяется как подмножество
входных символов ленты, причем е є (Г -
Σ);
одно
из состояний – q0 є Q является начальным
состоянием машины.
Решаемая
проблема задается путем записи конечного
количества символов из множества Σ є
Г – Si є Σ на ленту:
eS1S2S3S4...
... ... Sne
после
чего машина переводится в начальное состояние
и головка устанавливается у самого левого
непустого символа (q0,w) –, после чего в
соответствии с указанной функцией переходов
(qi,Si) - ->(qj,Sk, L или R) машина начинает заменять
обозреваемые символы, передвигать головку
вправо или влево и переходить в другие
состояния, предписанные функций переходов.
Остановка
машины происходит в том случае, если для
пары (qi,Si) функция перехода не определена.
Алан
Тьюринг высказал предположение, что любой
алгоритм в интуитивном смысле этого слова
может быть представлен эквивалентной
машиной Тьюринга. Это предположение известно
как тезис Черча–Тьюринга. Каждый компьютер
может моделировать машину Тьюринга (операции
перезаписи ячеек, сравнения и перехода
к другой соседней ячейке с учетом изменения
состояния машины). Следовательно, он может
моделировать алгоритмы в любом формализме,
и из этого тезиса следует, что все компьютеры
(независимо от мощности, архитектуры
и т.д.) эквивалентны с точки зрения принципиальной
возможности решения алгоритмических
задач.
Пример машины Тьюринга
Приведём пример МТ для умножения
чисел в унарной системе счисления. Запись правила «qiaj→qi1aj1R/L/N» следует
понимать так: qi — состояние
при котором выполняется это правило,
aj — данные в ячейке, в которой находится
головка, qi1 — состояние
в которое нужно перейти, aj1 — что нужно
записать в ячейку, R/L/N — команда на перемещение.
Машина работает по следующему
набору правил:
| |
q0 |
q1 |
q2 |
q3 |
q4 |
q5 |
q6 |
q7 |
q8 |
1 |
q01→q01R |
q11→q2aR |
q21→q21L |
q31 → q4aR |
q41→q41R |
|
|
q71→q2aR |
|
× |
q0×→q1×R |
|
q2×→q3×L |
|
q4×→q4×R |
|
q6×→q7×R |
|
q8×→q9×N |
= |
|
|
q2=→q2=L |
|
q4=→q4=R |
|
|
q7=→q8=L |
|
a |
|
|
q2a→q2aL |
q3a→q3aL |
q4a→q4aR |
|
q6a→q61R |
q7a→q7aR |
q8a→q81L |
* |
q0*→q0*R |
|
|
q3*→q6*R |
q4*→q51R |
|
|
|
|
| |
|
|
|
|
|
q5 →q2*L |
|
|
|
Описание состояний:
Начало |
q0 |
начальное состояние.
Ищем "x" справа. При нахождении переходим
в состояние q1 |
q1 |
заменяем "1" на
"а" и переходим в состояние q2 |
Переносим
все "1" из первого числа в результат |
q2 |
ищем "х" слева.
При нахождении переходим в состояние
q3 |
q3 |
ищем "1" слева,
заменяем ее на "а" и переходим в состояние
q4.
В случае если "1"
закончились, находим "*" и переходим
в состояние q6 |
q4 |
переходим в конец
(ищем "*" справа), заменяем "*"
на "1" и переходим в состояние q5 |
q5 |
добавляем "*"
в конец и переходим в состояние q2 |
Обрабатываем
каждый разряд второго числа |
q6 |
ищем "х" справа
и переходим в состояние q7. Пока ищем заменяем
"а" на "1" |
q7 |
ищем "1" или "="
справа
при нахождение "1"
заменяем его на "а" и переходим в
состояние q2 при нахождение "=" переходим
в состояние q8 |
Конец |
q8 |
ищем "х" слева.
При нахождении переходим в состояние
q9. Пока ищем заменяем "а" на "1" |
q9 |
терминальное состояние
(остановка алгоритма) |
Умножим с помощью МТ 3 на 2 в единичной
системе. В протоколе указаны начальное
и конечное состояния МТ, начальная конфигурация
на ленте и расположение головки машины
(подчёркнутый символ).
Начало. Находимся в состоянии
q0, ввели в машину данные: *111x11=*, головка
машины располагается на первом символе
*.
1-й шаг. Смотрим по таблице
правил что будет делать машина, находясь
в состоянии q0 и над символом
"*". Это правило из 1-го столбца 5-й
строки - q0*→q0*R. Это значит,
что мы переходим в состояние q0 (т.е. не меняем
его), символ станет "*" (т.е. не изменится)
и смещаемся по введённому нами тексту
"*111x11=*" вправо на одну позицию (R),
т.е. на 1-й символ 1. В свою очередь, состояние
q01 (1-й столбец 1-я строка) обрабатывается
правилом q01→q01R. Т.е. снова
происходит просто переход вправо на 1
позицию. Так происходит, пока мы не станем
на символ "х". И так далее: берём состояние
(индекс при q), берём символ, на котором
стоим (подчёркнутый символ), соединяем
их и смотрим обработку полученной комбинации
по таблице правил.
Простыми словами, алгоритм
умножения следующий: помечаем 1-ю единицу
2-го множителя, заменяя её на букву "а",
и переносим весь 1-й множитель за знак
равенства. Перенос производится путём
поочерёдной замены единиц 1-го множителя
на "а" и дописывания такого же количества
единиц в конце строки (слева от крайнего
правого "*"). Затем меняем все "а"
до знака умножения "х" обратно на
единицы. И цикл повторяется. Действительно,
ведь A умножить на В можно представить
как А+А+А В раз. Помечаем теперь 2-ю единицу
2-го множителя буквой "а" и снова
переносим единицы. Когда до знака "="
не окажется единиц - значит умножение
завершено.
Машина Тьюринга ,работающая на бесконечной
ленте
В качестве примера такого сведения
рассмотрим следующую теорему: Для любой машины
Тьюринга существует эквивалентная машина
Тьюринга, работающая на полубесконечной
ленте.
Рассмотрим доказательство,
приведённое Ю. Г. Карповым в книге «Теория
автоматов». Доказательство этой теоремы
конструктивное, то есть мы дадим алгоритм,
по которому для любой машины Тьюринга
может быть построена эквивалентная машина
Тьюринга с объявленным свойством. Во-первых
произвольно занумеруем ячейки рабочей
ленты МТ, то есть определим новое расположение
информации на ленте:
Затем перенумеруем ячейки,
причём будем считать, что символ «*» не
содержится в словаре МТ:
Наконец, изменим машину Тьюринга,
удвоив число её состояний, и изменим сдвиг
головки считывания-записи так, чтобы
в одной группе состояний работа машины
была бы эквивалентна её работе в заштрихованной
зоне, а в другой группе состояний машина
работала бы так, как исходная машина работает
в незаштрихованной зоне. Если при работе
МТ встретится символ ‘*’, значит головка
считывания-записи достигла границы зоны:
Начальное состояние новой машины
Тьюринга устанавливается в одной или
другой зоне в зависимости от того, в какой
части исходной ленты располагалась головка
считывания-записи в исходной конфигурации.
Очевидно, что слева от ограничивающих
маркеров «*» лента в эквивалентной машине
Тьюринга не используется.
Двумерные машины Тьюринга
Муравей Лэнгтона
Муравей Лэнгтона — это двумерная машина Тьюринга с очень простыми правилами,
изобретенная Крисом Лэнгтоном. Рассмотрим бесконечную плоскость,
разбитую на клетки, покрашенные некоторым
образом в чёрный и белый цвет. Пусть в
одной из клеток находится «муравей»,
который на каждом шаге может двигаться
в одном из четырёх направлений в клетку,
соседнюю по стороне. Муравей движется
согласно следующим правилам:
На чёрном квадрате — повернуть на 90° влево, изменить
цвет квадрата на белый, сделать шаг вперед
на следующую клетку.
На белом квадрате — повернуть на 90° вправо, изменить
цвет квадрата на чёрный, сделать шаг вперед
на следующую клетку.
Эти простые правила вызывают
довольно сложное поведение: после некоторого
периода довольно случайного движения
муравей, видимо, начинает непременно
строить дорогу из 104 шагов, повторяющуюся
бесконечно, независимо от изначальной
раскраски поля. Это наводит на мысль,
что «магистральное» поведение является аттрактором муравья Лэнгтона.
Муравей Лэнгтона также может
быть описан как клеточный автомат, в котором почти всё поле покрашено
в чёрно-белый цвет, а клетка с «муравьем»
имеет один из восьми различных цветов,
кодирующих соответственно все возможные
комбинации чёрного/белого цвета клетки
и направления движения муравья.
Существует простое расширение
муравья Лэнгтона, в котором используется
более двух цветов клеток. Цвета изменяются
циклически. Для таких муравьев существует
также простая форма названия: для каждого
следующего цвета используется буква L или R (Л и П), в зависимости от того, поворачивает
ли муравей направо или налево. Таким образом,
муравей Лэнгтона — это муравей RL.
Некоторые из этих обобщенных
муравьев Лэнгтона рисуют узоры, которые
становятся все более симметричными. Один из простых примеров —
муравей RLLR. Одно достаточное условие этого
заключается в том, что имя муравья, рассматриваемое
как циклический список, состоит из последовательных
пар повторяющихся букв LL или RR(цикличность списка означает,
что последняя буква может спариваться
с первой).
Заключение