- •Часть 2
- •Предисловие
- •Введение
- •1. Теория графов
- •1.1. Основные определения
- •1.2. Задачи поиска маршрутов (путей) в графе (орграфе)
- •1.3. Деревья и циклы
- •1.4. Транспортные сети
- •1.4.1. Поток в транспортной сети
- •1.4.2. Орграф приращений
- •Пример 1.21.
- •1.4.3. Алгоритм построения максимального потока в транспортной сети
- •Вопрос11. Укажите графы, которые всегда являются эйлеровыми:
- •Вопрос 12. Какая из нижеперечисленных формул для цикломатического числа является правильной?
- •Вопрос 13. Чему равна ?
- •Вопрос 36. Что является дополнением простого полного графа Кn?
- •Вопрос 37. Циклом называется:
- •Вопрос 38. Какой путь называется минимальным?
- •Вопрос 39. По таблице выяснить, какие из вершин являются центрами графа?
- •1.5. Сетевое планирование и управление
- •2. Теория автоматов
- •2.1. Конечные автоматы
- •2.2. Машина Тьюринга
- •3. Расчетно-графическое задание. Часть 2
- •3.1. Правила выполнения и оформления расчетно-
- •3.2. Задачи расчетно-графического задания. Часть 2
- •Пример выполнения расчетно-графического задания. Часть 2
- •Оглавление
2.2. Машина Тьюринга
Исторически понятие конечного автомата развилось из близкого понятия, введенного в 1936 году логиком Тьюрингом.
Машина Тьюринга является расширением конечного автомата и, согласно тезису Чёрча - Тьюринга, способна имитировать все другие исполнители (с помощью задания правил перехода), каким-либо образом реализующие процесс пошагового вычисления, в котором каждый шаг вычисления достаточно элементарен.
Тьюринг рассматривал гипотетическую «машину», имеющую конечное множество S внутренних состояний и одну бесконечно длинную ленту, разделенную на ячейки, которую машина могла передвигать на одну ячейку вправо или влево за такт. В каждой ячейке машина может записывать символ из конечного алфавита А. Первоначально лента должна быть пустой, кроме конечного числа ячеек, заполненных заранее. (Эти заранее заполненные ячейки можно представлять себе как программу запуска машины.)
В состав машины Тьюринга входит бесконечная в обе стороны лента (возможны машины Тьюринга, которые имеют несколько бесконечных лент), разделённая на ячейки, и управляющее устройство, способное находиться в одном из множества внутренних состояний. Число возможных состояний управляющего устройства конечно и точно задано. Управляющее устройство может перемещаться влево и вправо по ленте, читать и записывать в ячейки ленты символы некоторого конечного алфавита. Выделяется особый пустой символ, заполняющий все клетки ленты, кроме тех из них (конечного числа), на которых записаны входные данные. Управляющее устройство работает согласно правилам перехода, которые представляют алгоритм, реализуемый данной машиной Тьюринга. Каждое правило перехода предписывает машине, в зависимости от текущего состояния и наблюдаемого в текущей клетке символа, записать в эту клетку новый символ, перейти в новое состояние и переместиться на одну клетку влево или вправо. Некоторые состояния машины Тьюринга могут быть помечены как терминальные, и переход в любое из них означает конец работы, остановку алгоритма.
Основная разница между машиной Тьюринга и конечным автоматом состоит в том, что:
лента машины Тьюринга бесконечна;
машина Тьюринга может двигаться вдоль ленты (или смещать ленту) в любом направлении.
Это придает машине бесконечную память, которой можно пользоваться в ходе вычислений. Сверх того, каждую ячейку можно просматривать многократно.
Формальное определение машины Тьюринга существует в нескольких вариантах. Вот один из них.
Определение 2.2. Машиной Тьюринга называется пятерка объектов [A, S, , , ] следующего типа. Здесь
A={a0, a1, …, an} – конечный алфавит символов, которые могут быть записаны в ячейках и и являются одновременно входными и выходными;
S={s0, s1, …, sr} – конечное множество внутренних состояний;
: SAS – функция перехода (в следующее состояние);
: SAZ – функция выхода.
: SRd в множество { Л, П, ОСТАНОВ}.
Машина Тьюринга работает следующим образом. Она начинает работу, находясь в начальном состоянии s0. После считывания первого символа она переходит в новое внутренне состояние, определяемое функцией , записывает в ячейке символ, являющийся значением функции , перемещает ленту направо (П), налево (Л), или остается на месте и прекращает работу (ОСТАНОВ) в зависимости от значения функции .
На рисунке 2.7 схематически изображена лента машины Тьюринга и считывающая-записывающая головка.
Рис.2.7
Еще раз укажем, что работа машины состоит в повторении следующего цикла: считывание символа из ячейки, впечатывание нового символа в эту ячейку, выбор которого определяет функция (может оказаться, что это тот же символ), сдвиг ленты налево или направо или остановка. Лента бесконечна в обоих направлениях, однако вначале (и, значит, после любого такта) заполнено лишь конечное число ячеек.
Определение 2.3. Машина Тьюринга называется детерминированной, если каждой комбинации состояния и ленточного символа в таблице соответствует не более одного правила. Если существует пара «ленточный символ - состояние», для которой существует 2 и более команд, такая машина Тьюринга называется недетерминированной.
Пример 2.3.
Машина Тьюринга, описанная ниже, считывает входную последовательность нулей и единиц, выпечатывает Ч, если число единиц четное, и Н, если нечетное. Строке из нулей и единиц предшествуют и последуют пустые ячейки, обозначаемые . Символы Ч или Н печатаются в первой пустой ячейке вслед за входной строкой. Алфавит, таким образом, имеет вид A={ , 0, 1, Ч, Н}. Внутренние состояния S={s0, s1, s2}, s0 – начальное состояние. Машина останавливается по сигналу ОСТАНОВ.
: (S0, 0) s1 (S0, 1) s2 (S1, 0) s1 (S1, 1) s2 (S2, 0) s2 (S2, 1) s1 (S0 , ) s0 (S1 , ) s1 (S2, ) s2
|
: (S0, 0) 0 (S0, 1) 1 (S1, 0) 0 (S1, 1) 1 (S2, 0) 0 (S2, 1) 1 (S0 , ) (S1 , ) Ч (S2, ) Н
|
: (S0, 0) Л (S0, 1) Л (S1, 0) Л (S1, 1) Л (S2, 0) Л (S2, 1) Л (S0 , ) Л (S1 , ) ОСТАНОВ (S2, ) ОСТАНОВ
|
Удобнее задавать функции , , , пользуясь обозначениями Тьюринга. В этом варианте машина Тьюринга задается конечным множеством пятерок [si, ai, sr, zl, tn]. В каждой такой пятерке
si - текущее состояние машины;
ai - символ, считываемый из ячейки;
sr - следующее состояние машины;
zl - символ, печатаемый в ячейке;
tn - одна из команд П, Л, ОСТАНОВ.
В этих обозначениях описанная выше машина задается так:
S0 |
|
S0 |
|
Л |
S0 |
0 |
S1 |
0 |
Л |
S0 |
1 |
S2 |
1 |
Л |
S1 |
0 |
S1 |
0 |
Л |
S1 |
1 |
S2 |
1 |
Л |
S1 |
0 |
S2 |
0 |
Л |
S2 |
1 |
S1 |
1 |
Л |
S2 |
|
S1 |
Ч |
ОСТАНОВ |
S2 |
|
S2 |
Н |
ОСТАНОВ |
