Вопросы к зачету часть3 (Вопросы к зачету (ответы)), страница 2

Определение 3. Говорят, что НА в алфавите применим к слову в алфавите и перерабатывает его в слово , если существует конечная последовательность слов

(2)

в которой

или и слово не содержит подслов

В противном случае говорят, что алгоритм не применим к слову

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

Таким образом, НА в алфавите задает частичное отображение множества всех слов в алфавите в само себя. Выбирая различные схемы, мы будем получать различные НА.

Если - алфавит, содержащий , то НА в алфавите называется нормальным алгоритмом над алфавитом .

Приведем примеры нормальных алгоритмов. При этом буквой будет всегда обозначаться пустое слово (в любом алфавите).

1. НА в алфавите со схемой

перерабатывает любое слово в себя, причем последовательность слов, соответствующая слову имеет вид: .

1. НА со схемой

не применим ни к одному слову. Последовательность, соответствующая слову будет бесконечной:

1. НА в алфавите со схемой

приписывает к любому слову слева слово :

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

……………..

Последовательность слов, соответствующая произвольному слову в алфавите , для этого НА имеет вид:

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

так, что вся схема запишется в виде:

Заметим, что, выполняя свою задачу приписывания к словам из справа слова , мы совсем не интересовались переработкой слов в алфавите , содержащих букву . Здесь алгоритм будет действовать иначе. А именно, слово в алфавите , содержащее вхождений буквы , он будет перерабатывать в слово

где количество букв будет равно ,

где получается из удалением всех вхождений буквы (т. е. есть проекция в алфавит ).

5. Построим НА , перерабатывающий любое слово в перевернутое слово Для этого добавим к две новые буквы и возьмем следующую схему в алфавите

Проследите в качестве упражнения, что для любого слова в алфавите .

Приведем еще примеры НА над числами. Условимся натуральное число записывать в виде вертикальных палочек.

6. НА в алфавите со схемой

осуществляет сложение натуральных чисел.

7. НА в алфавите со схемой

осуществляет умножение натуральных чисел.

50. Определение Машины Тьюринга.

§ 2. МАШИНЫ ТЬЮРИНГА

В 1936 году независимо одна от другой появились работы английского математика А. Тьюринга и американского математика Э. Поста, в которых были даны уточнения понятия алгоритма или "эффективной процедуры" для решения массовых задач в терминах некоторых идеализированных вычислительных машин, называемых теперь машинами Тьюринга или Тьюринга-Поста. Устройства этих машин у А. Тьюринга и Э. Поста отличаются лишь несущественными деталями, а именно, процедура вычислений у Э. Поста раздроблена на более мелкие операции, чем у А. Тьюринга. В настоящее время в литературе описано много различных модификаций таких идеализированных машин. Мы далее рассмотрим одну из них, называя ее машиной Тьюринга (сокращенно МТ).

Машина Тьюринга, как и нормальный алгоритм, предназначается для переработки слов в некотором конечном алфавите , называемом внешним алфавитом машины. Слова в алфавите А записываются на ленту МТ, разбитую на ячейки, так, что в каждую ячейку записывается какая-либо одна буква алфавита А. Сама лента называется внешней памятью МТ. Предполагается, что лента в процессе работы может наращиваться, т.е. ленту можно считать потенциально бесконечной в обе стороны. Все вновь пристраиваемые ячейки заполняются символом , который называется пустым символом.

Переработка слов, записываемых на ленту МТ, осуществляется в дискретном времени по тактам, занумерованным натуральными числами, под действием так называемого управляющего устройства. Последнее в каждый такт может находиться в одном из конечного множества состояний

,

называемых внутренним состоянием.

Управляющее устройство связано с лентой так называемой считывающей головкой, которая в каждый такт находится против одной из ячеек ленты (обозревает одну ячейку). По команде управляющего блока, зависящей от внутреннего состояния и от содержимого обозреваемой ячейки, машина или останавливается или переходит в новое состояние, в последнем случае головка заменяет символ обозреваемой ячейки новым символом из А и остаётся против той же ячейки, или сдвигается на одну ячейку влево. При этом если головка обозревала последнюю (правую) ячейку ленты и ей дана команда сдвинуться вправо (влево), то к ленте справа (слева) автоматически добавляется новая ячейка с буквой . Оказавшись в состоянии , МТ прекращает работу ( называют стоп-состоянием).

Из приведённого описания видно, что положение МТ в каждый момент времени полностью определяется следующими параметрами:

1. словом, записанным на ленте;

2. внутренним состоянием;

3. номером обозреваемой ячейки.

Если в некотором такте работы МТ на её ленте записано слово , управляющее устройство находится в состоянии и головка обозревает ячейку с номером , то всю эту информацию можно записать одним, так называемым машинным, словом

(символ внутреннего состояния записывается перед буквой, записанной в обозреваемой ячейке). При переходе к новому такту машинное слово меняется согласно системе команд МТ. Изменения зависят от состояния МТ и от содержимого обозреваемой ячейки. Поэтому каждая команда записывается в виде формулы

, (1)

где - новое состояние, - буква, на которую заменяется (не исключается случай ), - одна из букв H, R, L, которые означают соответственно сохранение положения головки, сдвиг её на одну ячейку вправо, сдвиг на одну ячейку влево. Слова , называются соответственно левой и правой частями команды.

Подчеркнём, что система команд МТ удовлетворяет следующему единственному условию детерминизма: каждое слово вида (если не стоп-состояние) является левой частью ровно одной команды. Это условие позволяет всю систему команд МТ записать в виде таблицы.

Таблица 1.

Заметим, что в левых частях команд, а потому и во входной строке таблицы, состояние не участвует, поскольку в состоянии МТ прекращает работу.

Опишем теперь процесс преобразования слов в алфавите A описанной выше МТ с системой команд S.