Введение в схемы, автоматы и алгоритмы



Основные определения


Рассматриваемая в этом разделе модель алгоритмов была предложена английским математиком Тьюрингом в 1937г. еще до создания современных компьютеров компьютеров1)

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

Машина Тьюринга (м.Т.) состоит из неограниченной в обе стороны ленты, разбитой на ячейки, по которой передвигается головка машины. Такая "бесконечность" ленты является математической абстракцией, отражающей потенциальную неограниченность памяти вычислителя. Разумеется, в каждом завершающемся вычислении используется только конечная часть этой памяти - конечное число ячеек. В каждой ячейке ленты записан один символ из конечного внешнего алфавита машины ? = {a0, a1, … ,am }. Головка машины представляет конечный автомат, который в каждый момент времени находится в одном из внутренних состояний Q ={q0,q1,… , qn }. На каждом шаге головка в зависимости от своего внутреннего состояния и символа в ячейке, которую она наблюдает, изменяет свое внутреннее состояние и содержимое наблюдаемой ячейки и может сдвинуться на одну ячейку вправо или влево либо остаться на месте.

Дадим более формальное определение.

Определение 9.1. Машина Тьюринга - это система вида

включающая следующие компоненты:

  • Q ={q0,q1,… ,qn } - внутренний алфавит (алфавит состояний);
  • ? = {a0, a1, … , a{m-1} } - внешний алфавит (алфавит ленты);
  • P - программа машины, в которой для каждой пары qi

    Q \ { qf }, aj
    ? имеется (одна!) команда вида

    C

    {Л, П, Н} задает сдвиг головки вправо, влево или на месте;

  • q0
    Q - начальное состояние;
  • qf
    Q - заключительное состояние.


Выделим в алфавите ? специальный пустой символ a0 =
и будем считать, что во всех ячейках ленты, кроме конечного их числа, в начальный и во все последующие моменты находится пустой символ.

Будем говорить, что некоторый символ стирается, если он заменяется на пустой. Два слова из ?* будем считать равными, если они совпадают после отбрасывания всех пустых символов слева и справа. Например,
ab
c
=
ab
c = ab
c, но ab
c
abc.

Как и для конечных автоматов, программу P можно задавать с помощью таблицы размера n ? m, строки которой соответствуют состояниям из Q, а столбцы - символам из входного алфавита ?, в которой на пересечении строки qi и столбца aj стоит тройка qk al C - правая часть команды qi aj
qk al C.

Определение 9.2. Назовем конфигурацией м.Т.
в некоторый момент времени слово K= wл qi aj wп, где wл
?* - слово на ленте левее текушего положения головки, qi - внутреннее состояние в данный момент, aj- символ, обозреваемый головкой, wп
?* - слово на ленте правее текушего положения головки.

Будем считать, что слово wл aj wп содержит все значащие символы на ленте. Поэтому, с точностью до описанного выше равенства слов, конфигурация определена однозначно. В частности, если wл=?, т.е. пусто, то левее положения головки все ячейки пусты, а если wп=?, то правее положения головки все ячейки пусты.

Начальная конфигурация - это конфигурация вида q0w, т.е. в начальный момент времени головка в состоянии q0 обозревает первый символ входного слова w. { it Заключительная } конфигурация - это конфигурация вида w1 qf w2, в которой машина находится в заключительном состоянии qf .

Определение 9.3. Скажем, что конфигурация K= w1 qi aj w2 м.Т.
за один шаг (такт) переходит в конфигурацию
если в программе имеется команда qi aj
qk al C и при этом,

  • если С=Н, то w1'=w1, w2'=w2 и a{j'}=al;
  • если С=Л, то w1=w1' a, a{j'}=a, w2'=al w2 (если w1=?, / то w1' = ? и a{j'}=
    );
  • если С=П, то w2=aw2', a{j'}=a, w1'=w1 al (если w2=?, / то w2' = ? и a{j'}=
    ).


Как обычно, через
обозначим рефлексивное и транзитивное замыкание отношения
а
будет означать, что конфигурация K за n шагов переходит в K'. (Если из контекста ясно, о какой машине идет речь, то индекс
будем опускать).


Содержание    Вперед





Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий