Машина Тьюринга. Устройство. Состояние. Конфигурация.

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

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

Как и в машине Поста, лента разбита на отдельные ячейки, однако, в машине Тьюринга неподвижной является головка, а лента передвигается относительно нее вправо или влево. Другим отличием является то, что она работает не в двоичном, а некотором произвольном конечном алфавите А={Δ, а1, ..., ап} - этот алфавит называется внешним. В нем выделяется специальный символ - Δ, называемый пустым знаком. В каждую ячейку ленты может быть записан лишь один символ. Информация, хранящаяся на ленте, изображается конечной последовательностью знаков внешнего алфавита, отличных от пустого знака.

Головка всегда расположена над одной из ячеек ленты. Работа происходит тактами (шагами). В машине Тьюринга реализуется система предельно простых команд обработки информации. Эта система команд обработки дополняется также предельно простой системой команд перемещений ленты: на ячейку влево, на ячейку вправо и остаться на месте, т.е. адрес обозреваемой ячейки в результате выполнения команды может либо измениться на 1, либо остаться неизменным. Элементарность этих команд означает, что при необходимости обращения к содержимому некоторой ячейки, она отыскивается только посредством цепочки отдельных сдвигов на одну ячейку. Разумеется, это значительно удлиняет процесс обработки, зато позволяет обойтись без нумерации ячеек и использования команд перехода по адресу, т.е. сокращает количество истинно элементарных шагов, что важно в теоретическом отношении.

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

Понимать схему необходимо следующим образом: на такте i на один вход ЛУ подается знак из обозреваемой в данный момент ячейки (аi), а на другой вход - знак, обозначающий состояние ЛУ в данный момент (qi). В зависимости от полученного сочетания знаков (аi, qi} и имеющихся правил обработки ЛУ вырабатывает и по первому выходному каналу направляет в обозреваемую ячейку новый знак (аi+1), подает команду перемещения головки (Di+1 из R, L и S), а также дает команду на вызов следующего управляющего знака (qi+1). Таким образом, элементарный шаг (такт) работы машины Тьюринга заключается в следующем: головка считывает символ из обозреваемой ячейки и, в зависимости от своего состояния и прочитанного символа, выполняет команду, в которой указано, какой символ записать (или стереть) и какое движение совершить. При этом и головка переходит в новое состояние.

В схеме функционирования машины Тьюринга отражено разделение памяти на внешнюю и внутреннюю. Внешняя представлена, как указывалось, в виде бесконечной ленты - она предназначена для хранения информации, закодированной в символах внешнего алфавита. Внутренняя память представлена двумя ячейками для хранения следующей команды в течение текущего такта: в Q передается из ЛУ и сохраняется следующее состояние (qi+1), а в D - команда сдвига (Di+1). Из Q по линии обратной связи qi+1 поступает в ЛУ, а из D команда поступает на исполнительный механизм, осуществляющий при необходимости перемещение ленты на одну позицию вправо или влево.

Общее правило, по которому работает машина Тьюринга, можно представить следующей записью: qiaj® , т.е. после обзора символа аj головкой в состоянии qi, в ячейку записывается символ аj’, головка переходит в состояние qi', а лента совершает движение Dk.

Конкретная машина Тьюринга задается перечислением элементов множеств А и Q, а также, логической функцией, которую реализует ЛУ, т.е. набором правил преобразования. Ясно, что различных множеств A, Q и логических функций может быть бесконечно много, т.е. и машин Тьюринга также бесконечно много.

Совокупность состояний всех ячеек ленты, состояния ЛУ и положение головки называется конфигурацией машины

58. Нормальные алгоритмы Маркова. Сравнение алгоритмических схем Маркова и Тьюринга.

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

Рассмотрим некоторый алфавит А, содержащий конечное число знаков (букв). Введем ряд определений:

Слово – это любая конечная последовательность знаков алфавита.

Число символов в слове называется его длиной.

Слово, длина которого равна нулю, называется пустым.

Слово s называется подсловом слова q, если q можно представить в виде q=rst, где r и t – любые слова в том же алфавите (в том числе и пустые).

Теперь можно определить понятие алгоритма (не являющееся строгим):

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

В алгоритмах Маркова в качестве элементарного шага алгоритма принимается подстановка одного слова вместо другого. Пусть в алфавите А построено исходное слово Р, которое содержит подслово Р_r (в общем случае таких подслов в исходном слове может быть несколько), а также имеется некоторое слово P_k в том же алфавите.

Подстановкой называется замена первого по порядку подслова Р_r исходного слова Р на слово P_k. Обозначается подстановка P_r ® P_k.

Алгоритм в данной форме представления задается системой подстановок, которая представляет собой последовательность (список) подстановок. Если в этом списке имеются подстановки с левыми частями, которые входят в Р, то первая из нихприменяется к Р, в результате чего оно переходит в другое слово Р₁. К нему вновь применяется схема подстановок и т.д. Процесс прекращается в двух случаях: либо в списке не нашлось подстановки с левой частью, входящей в Р_п, либо при получении Р_п была применена последняя подстановка.

Пример.

Пусть задан алфавит А ={*, 1} и единственная подстановка: *1®1. Найти результат обработки, если исходным является слово Р = 11*111*1. Применение нормального алгоритма с указанной подстановкой к данному слову дает последовательность (подчеркиванием выделяется преобразуемая комбинация):

11*111*1®11111*1®111111, т.е. алгоритм находит количество единиц в исходном слове (суммирует числа в унарной системе счисления).

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

⇐ Предыдущая 7 8 9 10 111213 14 15 16 Следующая ⇒