Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Функционирование машины Тьюринга






Понятие машины Тьюринга и ее функционирование

Устройство одноленточной машины Тьюринга включает в себя:

Внешний алфавит А - конечное множество символов. В этом алфавите в виде слова кодируется та информация, которая подается в машину. Машина преобразует информацию, поданную в виде слова, в новое слово.

Внутренний алфавит (внутренняя память машины), состоящий из конечного множества состояний

Q= { q 0, q 1 ,..., qm } .

Два состояния имеют особое назначение: q 1начальное состояние машины, q 0заключительное состояние. Остальные состояния вместе с начальным состоянием называются рабочими состояниями.

Алфавит сдвиговS = { l, s, r }, где l, s, r соответственно означают сдвиг некоторого символа влево, оставить символ на месте, сдвиг символа вправо.

Кроме того, в конфигурации машины имеются:

А) бесконечная в обе стороны лента (внешняя память машины). Она разбита на клетки. В каждую клетку может быть записана только одна буква из алфавита А, включая пустой символ (пробел), который мы будем обозначать через а0.

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

В одном такте работы машины управляющая головка может сдвигаться влево или вправо только на одну клетку или может оставаться на месте;

в) устройство управления, которое управляет работой машины с помощью программы;

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

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

Последовательность шагов машины Тьюринга определяется следующим образом: для любого внутреннего состояния qi и символа аj однозначно заданы:

o а) следующее состояние qt;

o б) буква аv, которую нужно записать вместо аj в ту же ячейку (стирание символа будем понимать как запись пустого символа а 0);

o в) направление сдвига головки dk, обозначаемое одним из символов l, s, r.

Это задание может описываться либо системой правил (команд), имеющих вид:

qiаj→ qtavdk, (*)

либо таблицей, строкам которой соответствуют состояния, столбцам – входные символы, а на пересечении строки qi и столбца аj записана тройка символов qtаvdk, и, наконец, диаграммой переходов (орграфом).

На этой диаграмме состояниям соответствуют вершины, а команде вида (*) – дуга, ведущая из вершины qi в вершину qt, на которой написано аjavdk. Условие однозначности требует, чтобы для любого j и любого i ¹ 0 в системе команд имелась одна команда, аналогичная команде (*) с левой частью qiaj; состояние q 0 в левых частях команд не встречается.

На диаграмме переходов это выражается условием, что из каждой вершины, кроме q 0, выходит ровно n дуг, причем на разных дугах левые части различны; в вершине q 0 нет выходящих дуг.

Из отдельных команд машины Тьюринга составляется программа этой машины.

Программа машины Тьюринга – это отображение

f: A × Q \ { q 0} → A × Q × S,

то есть правило, сопоставляющее любой паре (аj, qi), i ¹ 0, тройку (аv, qt, dk), как было описано выше.

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

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

Машина никогда не останавливается. Тогда говорят, что машина не применима к начальной информации (проблема остановки).

Функционирование машины Тьюринга

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

Головка считывает букву, находящуюся в обозреваемой ячейке. Устройство управления обращается к программе машины, находит в таблице клетку, соответствующую считанной букве и состоянию машины. Пусть в этой клетке находится тройка (аv, qt, dk).


Поделиться с друзьями:

mylektsii.su - Мои Лекции - 2015-2024 год. (0.007 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал