Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Элементы модели алгоритма:
Основные ограничения на элементы модели:
Задание конкретных элементов модели алгоритма, удовлетворяющих этим ограничениям, определяет конкретную математическую модель, которую можно анализировать средствами математики.
Машины Тьюринга.
Эта модель алгоритма была впервые предложена А.М. Тьюрингом в 1936 г.
Машина Тьюринга имеет 3 алфавита:
В конструкции машины имеются:
1) бесконечная лента (разбитая на ячейки), предназначенная для размещения бесконечных записей конечных слов над алфавитом А. В каждой ячейке м.б. записан 1 из символов алфавита А. Пустая ячейка – такая ячейка, в которую помещен некоторый фиксированный символ (пробел, ноль,…). Следовательно, в каждый данный момент времени лента полностью заполнена.
2) механизм – считывающе-записывающее устройство (СЗУ), называемое также читающей/пишущей головкой. СЗУ обладает способностью обозревать одну ячейку ленты, считывать букву, записанную в ячейке, заносить на место считываемой любую другую букву внешнего алфавита; за один такт работы головка может переместиться на 1 ячейку вправо (R) или на 1 ячейку влево (L) и воспринимать новую ячейку или остаться на месте (S).
3) устройство управления (УУ), которое управляет с помощью программы работой машины.
4) программа машины, определяющая переходы машины от одной конфигурации к другой.
Правила работы машины (правила обращения УУ с программой и СЗУ )
Машина работает дискретно (пошагово). На каждом шаге происходит переход от одной конфигурации к другой.
Перед налом работы машина находится в начальной конфигурации: СЗУ обозревает первую букву слова, а машина находится в начальном состоянии . СЗУ считывает букву, находящуюся в обозреваемой ячейке. УУ обращается к программе машины: находит клетку, соответствующую считанной букве и состоянию машины. Пусть в этой клетке находится тройка , тогда буква а заносится обозреваемую ячейку, машина переводится в состояние q, а СЗУ совершает сдвиг на 1 ячейку влево, если , вправо – при , и остается на месте, если . На этом завершена работа машины на первом шаге и она готова к выполнению следующего аналогичного шага. Работа машины продолжается до тех пор, пока на каком-то из шагов машины не придет в состояние . УУ в этом случае останавливает машину. Возникшая конфигурация называется заключительной, а полученное слово – результатом применения машины к исходному слову.
Итак, правила работы машины: : если машина находится в состоянии , головка обозревает ячейку, в которой записан символ . Символ заменяется на , после этого головка делает движение Т и переходит в состояние .
Если u – исходное слово, Т – машина, то через Т(u) обозначают результат.
Опр. Говорят, что МТ неприменима к слову u, если в процессе применения ее к слову она ни на каком из шагов не приходит в заключительное состояние.
Замечания.
F – функция выхода
G – функция входа
D – функция движения головки.
С использованием этих функций программу для МТ можно представить в виде списка, элементы которого – последовательности вида: .
2) каждому элементу из множества состояний поставим в соответствие вершину, помеченную этим символом. Если есть команда: то из вершины в направим ориентированное ребро с меткой . Тогда программе МТ будет поставлен в соответствие связный ориентированный мультиграф с помеченными ребрами. Он называется диаграммой состояний МТ.
.
Последующее поведение МТ (с некоторого момента времени) полностью определено, если известно:
Конфигурация МТ – слово вида , где – состояние МТ, слово, записанное на ленте слева от положения, занятого головкой, слово, записанное на ленте справа от .
Выделяется начальная конфигурация и конечная: .
Пусть есть конфигурация К. Если в ней применить соответствующую инструкцию, возникнет новая конфигурация .
Говорят, что непосредственно получается (выводима) из К.
Пусть есть конфигурации: (каждая следующая выводится из предыдущей): : конф. выводима из .
Если - начальная конфигурация, то последовательность конфигураций называется тьюринговым вычислением
Если есть и , говорят, что данная МТ применима к входному слову .
Если последовательность конфигураций бесконечна, то МТ неприменима к входному слову.
Пример. Пусть программа машины Тьюринга имеет вид: .
Предъявим машине ленту, которую она воспринимает в состоянии , как показано на рисунке:
Работа МТ:
Работа МТ продолжается бесконечно, т.е. МТ неприменима к входному слову.
0
0
0
0
…………..
…………..
0
0
0
0
0
0
0
…………..
…………..
0
0
0
1
0
0
0
…………..
…………..
0
0
0
1
0
0
0
…………..
…………..
0
0
0
1
0
1
0
…………..
…………..
0
0