Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10  11 | Следующая страница реферата

Правило начала.

Правило окончания.

Правило определения расположения результата.

Здесь в качестве примеров уточнения понятия алгоритма мы рассмотрим Машину Тьюринга и Нормальные алгоритмы Маркова.

Машина Тьюринга.

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

В качестве исполнителя алгоритмов им был предложен автомат, состоящий из:

бесконечной ленты, разбитой на ячейки;

каретки, способной передвигаться над лентой, от ячейки к ячейке, считывать символы, записанные на ленте, записывать символы в ячейки.

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

считать символ из ячейки, над которой она находится;

записать символ в ячейку, над которой она находится;

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

изменять свое внутреннее состояние.

Поясним последний пункт. Предполагается, что каретка может находиться в одном из состояний, из определенного множества состояний. Одним из ее действий, на ряду с перечисленными выше, является переход из одного состояния в другое.

В терминах, упомянутых выше семи параметров машину Тьюринга можно определить следующим образом.

Совокупность возможных исходных данных - алфавит D;

Совокупность возможных результатов - алфавит D;

Совокупность возможных промежуточных результатов - алфавит D;

Множество действий:

множество правил вида ap®bqw, где a,bÎ D;  p,qÎ Q;  wÎ {Л, П, Н}.

D - алфавит символов, которые могут появляться на ленте;

Q - множество символов, обозначающих состояния каретки.

Л, П, Н - символы, обозначающие передвижение каретки налево, направо или наместе соответственно.

Смысл правила  ap®bqw  состоит в следующем. Если каретка находится над ячейкой, в которой записан символ а, и каретка находится в состоянии p, то каретка должна:

записать в эту ячейку символ b (символ а при этом стирается),

Рекомендуем скачать другие рефераты по теме: шпоры на экзамен, реферат по математике.





Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10  11 | Следующая страница реферата