Всего на сайте:
236 тыс. 713 статей

Главная | Информатика

Основные определения., Вступление. Характеризуя понятие алгоритма, отмечено, что предпис..  Просмотрен 97

Вступление.

Характеризуя понятие алгоритма, отмечено, что предписание, задающее алгоритм, должно быть составлено таким образом, чтобы его исполнение было во всех деталях однозначно осуществимо и не требовало никаких свободно принимаемых решений. Другими словами, исполнитель алгоритма должен действовать согласно предписанию совершенно механически, «машинально», не вкладывая в свою работу никакой инициативы, изобретательности. Но что или кто может в наибольшей степени обладать таким свойством? Конечно же, машина.

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

[E1] Это воображаемая «машина» (в кавычках потому, что она вовсе не похожа на реальную машину с множеством деталей из металла, пластмассы или других материалов) — машина «на бумаге» или математическая модель машины.

[E2] Дадим описание машины Тьюринга. Потом покажем, каким образом ее можно определить как математическое понятие.

Основные определения.

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

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

Во-вторых, машина Тьюринга снабжена потенциально бесконечной памятью. Что значит «потенциально бесконечная память»? Это значит, что хотя в каждый момент ее память хранит лишь конечное количество информации, однако для этого количества информации нет никакой верхней границы. [E3] Вообразим такую память машины Тьюринга в виде ленты, разделенной на клеточки — ячейки памяти, — которая может быть продолжена вправо сколько угодно (рис.).

[E4]

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

Ради удобства договоримся: когда ячейка пустая, считать, что в ней хранится специальная буква алфавита, которую мы обозначим через s0 и назовем пустой буквой. [E6] Таким образом, в каждой ячейке ленты в любой данный момент находится одна и только одна буква алфавита А = {s0, s1, s2, ... ,sk}, причем только конечное число ячеек заполнено буквами из А, отличными от пустой буквы s0.[E7]

Машина Тьюринга снабжена (в нашем воображении) управляющей головкой, которая в каждый момент обозревает (воспринимает) лишь одну ячейку памяти и может изменить информацию, находящуюся в ней. [E8] Представить это можно следующим образом: если в какой-то момент букву в обозреваемой ячейке нужно заменить другой, то старая буква стирается и в ячейку вписывается новая (так же, как на магнитофонной ленте при новой записи автоматически стирается старая запись). Если эту операцию записать в общем виде «si®sj», т. е. буква si заменена буквой sj[E9] , то можно выделить следующие частные случаи:

а) i = j, т. е. буква в обозреваемой ячейке не изменилась;

б) i ¹ j – буква изменилась, при этом:

б1) если i = 0, то в пустую ячейку вписана буква sj, и б2) если j = 0, то стерта буква si в обозреваемой ячейке.

Управляющая головка за один такт работы машины может также передвинуться влево и воспринимать соседнюю слева ячейку (этот сдвиг головки будем обозначать через Л), управляющая головка может передвинуться вправо и воспринимать соседнюю справа ячейку (этот сдвиг мы обозначим через П), управляющая головка может остаться на месте и воспринимать ту же ячейку (этот «сдвиг» обозначим через Н). [E10] На рисунке изображен фрагмент ленты, а также управляющая головка. В обозреваемой ячейке хранится буква si.

Машина Тьюринга имеет конечное множество внутренних состояний: Q = {q0, q1, q2, …, qm}. В каждый данный момент времени машина Тьюринга находится в одном из своих внутренних состояний.

После выполнения очередного такта работы машина может изменить свое внутреннее состояние и воспринимать ячейку в следующий момент уже в новом состоянии.[E11] Разумеется, внутреннее состояние может остаться и прежним. Если машина в какой-то момент времени попадет в состояние q0, то ее работа заканчивается (состояние q0 называется пассивным). Из множества Q выделим еще одно состояние — q1начальное состояние. В этом состоянии машина всегда начинает свою работу.[E12]

Что умеет воображаемая машина?

За один такт работы она может:

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

2) совершить сдвиг влево или вправо на одну ячейку или остаться на месте и

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

И больше машина Тьюринга ничего не умеет делать.[E13]

 

Может показаться, что это очень мало. В действительности, это очень много.

Порядок работы машины Тьюринга с алфавитом A={s0, s1, s2, …, sk} и множеством состояний Q = {q0, q1, q2, ..., qm} полностью определяется программой, представляющей собой таблицу, содержащую k+1 столбец и m строк. В клетке таблицы на пересечении i-го столбика (i=0, 1, 2, ..., k) и j-й строки (j=1, 2, ..., m) вписана команда, которую должна выполнить машина Тьюринга.

[E14] Таблица 1

[E15]

Если машина в какой-то момент воспринимает управляющей головкой ячейку, в которой записана буква si, и машина находится в состоянии qj, команда будет записываться в виде трехбуквенного слова shTqp, где ТÎ{Л, Н, П}, т. е. обозначает один из сдвигов управляющей головки.

[E16]

Для выполнения команды машина проделывает следующую работу:

1) буква si, находящаяся в обозреваемой ячейке, меняется на sh;

2) управляющая головка совершает сдвиг Т, т. е. Л, Н или П;

3) машина переходит в состояние qp.

[E17]

Работа машины состоит из тактов, выполняемых в строгом соответствии с программой. Если в какой-то момент времени машина приходит в состояние q0, то работа машины заканчивается. Программа полностью определяет работу машины, поэтому можно сказать, что машина Тьюринга задана, если задана ее программа.[E18]

Предыдущая статья:СЦЕНА ТРЕТЬЯ Следующая статья:Пример.
page speed (0.1152 sec, direct)