Определение алгоритма. Машины Поста и Тьюринга.

⇐ ПредыдущаяСтр 3 из 34Следующая ⇒

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

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

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

Машина Поста — абстрактная вычислительная машина, способная выполнять лишь самые элементарные действия.

Машина Поста состоит из ленты и каретки (называемой также считывающей и записывающей головкой). Лента бесконечна и разделена на секции одинакового размера — ячейки. В каждой ячейке ленты может быть либо ничего не записано, либо стоять метка V. Информация о том, какие ячейки пусты, а какие содержат метки, образует состояние ленты.

Каретка может передвигаться вдоль ленты влево и вправо. Когда она неподвижна, говорят, что каретка обозревает одну ячейку. За единицу времени каретка может совершить одно из трех действий: стереть метку, поставить метку, совершить движение на соседнюю ячейку. Состояние машины Поста складывается из состояния ленты и положения каретки.

Действия каретки подчинены программе, состоящей из перенумерованного набора команд. Команды бывают шести типов:

· записать 1 (метку), перейти к i-й строке программы;

· записать 0 (стереть метку), перейти к i-й строке программы;

· сдвиг влево, перейти к i-й строке программы;

· сдвиг вправо, перейти к i-й строке программы;

· останов;

· если 0, то перейти к i, иначе перейти к j.

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

В каждой машине Тьюринга есть неограниченная в обе стороны лента, разделенная на ячейки, и автомат - головка для считывания/записи, управляемая программой.

С каждой машиной Тьюринга связаны два конечных алфавита: алфавит входных символов A = {a₀, a₁, ..., a_m} и алфавит состояний Q = {q₀, q₁, ..., q_p}. Состояние q₀ называется пассивным, если машина попала в это состояние, то она закончила свою работу. Состояние q₁ называется начальным. Находясь в этом состоянии, машина начинает свою работу.

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

В зависимости от того, какую букву a_i видит, а также в зависимости от своего состояния q_j автомат может выполнять следующие действия:

· записать новую букву в обозреваемую ячейку;

· выполнить сдвиг по ленте на одну ячейку вправо/влево или остаться неподвижным;

· перейти в новое состояние.

В процессе работы автомат будет перескакивать из одной ячейки в другую, пока не дойдет до той, в которой записано, что автомат должен перейти в состояние q₀. Эти ячейки называются ячейками останова. Дойдя до любой такой ячейки, машина Тьюринга останавливается.

Нормальные алгоритмы Маркова (НАМ). Основные приемы и особенности составления НАМ.

Нормальный алгоритм Маркова (НАМ, также марковский алгоритм) — один из стандартных способов формального определения понятия алгоритма.

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

НАМ представляют собой класс алгоритмов, применимых к словам некоторого алфавита. Каждый НАМ определяется указанием алфавита, в котором он действует, и схемы НАМ. Алфавитом НАМ может служить любой конечный алфавит A. Формулой подстановки в алфавите A называется выражение типа p → q (простая подстановка, в эмуляторе обозначена как ->) или p ↦ q (заключительная подстановка, в эмуляторе обозначена как =>), где p и q — некоторые слова в алфавите A, называемые, соответственно, левой и правой частями формулы подстановки. Каждый НАМ в алфавите A имеет конечное число формул подстановки. Их записывают в виде списка, который называется схемой алгоритма.

Марковской подстановкой называется операция над словами, задаваемая с помощью упорядоченной пары слов (P, Q), состоящая в следующем. В заданном слове R находят первое вхождение слова P (если таковое имеется) и, не изменяя остальных частей слова R , заменяют в нем это вхождение словом Q. Полученное слово называется результатом применения марковской подстановки (P, Q) к слову R . Если же первого вхождения P в слово R нет (а, следовательно, вообще нет ни одного вхождения P в R), то считается, что марковская подстановка (P, Q) неприменима к слову R .

Применение НАМ к некоторому слову S заключается в следующем. В списке формул подстановки ищется первая из тех формул, в которой левая часть входит в S. Находится 1-е вхождение левой части формулы в S и вместо этого вхождения подставляется правая часть формулы. Получается новое слово S'. Cо словом S' производятся те же действия и т.д.

Данный процесс обрывается в 2-х случаях:

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

- в слово не входит ни одна из левых частей формул подстановки.

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

Дата добавления: 2018-08-06; просмотров: 1631; Мы поможем в написании вашей работы!

Поделиться с друзьями:

⇐ Предыдущая 1 234 5 6 7 8 9 10 Следующая ⇒

Мы поможем в написании ваших работ!