Мой помощник - компьютер 2010
Первый этап. 11 января - 25 января
Задания первого этапа:
До 25 января отправьте заявку участника по электронной почте на адрес scpinerPVV@yandex.ru, тема письма: Машина Тьюринга. В заявке необходимо указать: ФИ участника, образовательное учреждение, класс, ФИО учителя-консультанта, электронный адрес для обратной связи.
Зарегистрируйтесь на сайте http://konkyrcy.ucoz.ru/
На этом сайте зайдите в раздел Форум. В форуме Первого этапа "Давайте знакомиться" кратко расскажите о себе.
Изучите теорию по теме «Машина Тьюринга»
Программу можно установить на свой ПК, и решения всех задач конкурса можно будет проверять с помощью этого приложения. Для единообразия решений оформлять алгоритмы в рамках конкурса будем в виде таблиц.
Справка
Английским математиком А.Тьюрингом (1912-1954) для построения формального определения алгоритма в 1936 году была предложена абстрактная вычислительная конструкция, которая позже была названа «машиной».
Описание машины Тьюринга
Машина Тьюринга — это строгое математическое построение, математический аппарат, созданный для решения определенных задач. Он был назван "машиной" потому, что по описанию его составляющих частей и функционированию он похож на вычислительную машину или автоматическое устройство.
В машине Тьюринга есть две части:
1) неограниченная в обе стороны лента, разделенная на ячейки; в каждой ячейке может быть записан ровно один символ;
2) автомат, головка для считывания/записи, управляемая программой. Автомат имеет одну ячейку памяти, в которой хранится символ состояния.
Принципиальное отличие машины Тьюринга от реальных вычислительных машин состоит в том, что ее запоминающее устройство – лента – бесконечно, а значит, имеет бесконечную емкость: у реальных компьютеров запоминающее устройство может быть очень большим, но обязательно конечным. По этой причине реализовать машину Тьюринга на реальных компьютерах в полной мере невозможно, и в этом смысле она мощнее любой реальной вычислительной машины.
У каждой машины Тьюринга есть два конечных алфавита: алфавит входных символов (символов ленты) А = {а0, ..., аm} и алфавит состояний Q = {q0, q1,..., qn}. Для разных машин Тьюринга (т.е. задач) могут использоваться разные алфавиты A и Q.
Во множестве состояний обязательно есть два специальных элемента — состояния q0 и q1. Состояние q0 называется пассивным, или состоянием останова. Если машина попала в состояние q0, то она завершает свою работу. Состояние q1 называется начальным. Когда машина Тьюринга начинает свою работу, она находится в состоянии q1.
Алфавит входных символов А обязательно содержит один специальный символ а0 — так называемая пустая буква (часто обозначается _), который используется как признак того, что "ячейка пуста".
Входное слово размещается на ленте, по одной букве в расположенных подряд ячейках. Слева и справа от входного слова находятся только пустые ячейки (заполненные пустыми буквами а0). Ячейки ленты не имеют номеров или каких-либо пометок.
В каждый момент времени автомат просматривает только одну ячейку ленты. Он может: прочитать букву из текущей ячейки, записать букву в текущую ячейку, переместиться на одну ячейку влево (Л) или вправо (П), либо остаться на месте (Н).
Ячейка памяти хранит так называемое "состояние машины Тьюринга". Машина Тьюринга может записывать в нее только символы из алфавита состояний. Состояния нужны для того, чтобы обозначать различные шаги программы.
Программа машины Тьюринга
Программа машины Тьюринга состоит из набора правил вида: "если текущее состояние равно qi и из текущей ячейки считан символ аi, то в текущую ячейку следует записать символ аj, перевести машину в состояние qj и передвинуть автомат в направлении dj. При этом для каждой команды исходное состояние qi может быть любым из множества Q, кроме состояния останова q0, конечное состояние команды qj — любым из Q, символы а — любые из алфавита ленты А, а направление перехода d — элемент из множества {Л, П, H} (Л — влево, П — вправо, Н — неподвижен).
Для записи программы машины Тьюринга обычно используют одну из двух форм:
либо список команд, записанных в формате {ai, qi} → {аj, dj, qj},
либо таблица, у которой столбцы проиндексированы символами алфавита ленты а, строки — символами алфавита состояний q, а в каждой ячейке таблицы записана тройка {a, d, q} — символ, который надо записать в текущую ячейку, направление перехода и новое состояние машины Тьюринга. Состояния qi и qj, а также символы аi и аj могут совпадать.
|
