О подходах к уточнению понятия алгоритма.

Понятия, использованные в сформулированных выше требованиях к алгоритму, такие, как ясность, элементарность, четкость, сами нуждаются в уточнении. Очевидно, что их словесные определения будут содержать новые понятия, которые снова потребуют уточнения и т.д. Поэтому в теории алгоритмов применяется другой подход: выбирается конечный набор исходных объектов, которые объявляются элементарными, и конечный набор способов построения из них новых объектов. Этот подход уже был использован при обсуждении вопросов о данных: уточнением понятия «данные» в дальнейшем будем считать множество слов в конечных алфавитах.

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

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

Известные стандартизации понятия алгоритма включают:

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

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

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

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

С точки зрения инженерной практики наиболее подходящей для исследования алгоритмичности задачи является модель, называемая машиной Тьюринга, созданная в 30-х годах XX века [5]. Тьюринг предложил гипотетическое автоматическое устройство, которое сейчас называется машиной Тьюринга, и определил алгоритм как программу этой машины. Алгоритм интерпретируется как некоторое детерминированное устройство, способное выполнять в каждый отдельный момент лишь весьма примитивные операции. Такое представление не оставляет сомнений в однозначности алгоритма и элементарности его шагов. Кроме того, эвристика этой модели близка к ЭВМ и, следовательно, к инженерной интуиции.

Алан Тьюринг сформулировал тезис, связывающий понятие алгоритма и машины: «Для всякого (неформального) алгоритма может быть построен Тьюрингов алгоритм (программа машины Тьюринга (МТ)), дающий при одинаковых исходных данных тот же результат» [5].

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

Теория алгорифмов Маркова- алгоритмическая модель, использующая преобразования слов в произвольных алфавитах, в которых элементарные операции-это подстановки цепочек символов, т.е. замены части слова (подслова) другим словом. Такие алгоритмы называются вербальными алгорифмами. Вербальный алгорифм – это неформальное понятие. Процесс работы такого алгорифма в алфавите А состоит в последовательном порождении слов в алфавите А согласно предписанию. Работа начинается с некоторого исходного слова (входные данные) и заканчивается порождением слова-результата. Если для слова Р процесс заканчивается некоторым результатом Q, то говорят, что алгорифм a применим к слову Р. Запись a: P ® Q позволяет дать точное определение нормального алгорифма.

Удивительным научным результатом является доказательство эквивалентности всех формальных определений алгоритма. Эквивалентность двух абстрактных моделей алгоритма состоит в том, что любой класс проблем, который может быть решен с помощью моделей одного типа, можно решить и на моделях другого типа. В связи с этим в информатике получило признание следующее утверждение: «Любое разумное определение алгоритма, которое может быть предложено в будущем, окажется эквивалентным уже известным определениям». Исторически Алонзо Черч первый предложил отождествить интуитивное понятие алгоритма с одним из эквивалентных между собой точных определений. Алан Тьюринг независимо высказал предположение, что любой алгоритм может быть представлен машиной Тьюринга. Это предложение известно как тезис Черча-Тьюринга. Тезис Черча-Тьюрингапросто отражает уверенность в том, что разработанные формальные модели алгоритма достаточно полно представляют его интуитивное понимание.

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

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

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

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

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

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

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

Лента разбита на ячейки. Во всякой ячейке в каждый дискретный момент времени находится один символ алфавита А={a₀,a₁,a₂,...,a_n}, n ³ 1. В множестве символов алфавита выделяют пустой символ. Любая ячейка, содержащая пустой символ, называется пустой ячейкой. В качестве пустого символа обычно используется L. В некоторых случаях различают входной и выходной алфавит. Говорят, что рабочий алфавит А_раб есть объединение А_раб=А_inÈA_outÈ{L}, где А_in - входной алфавит, A_out - выходной алфавит.

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

Управляющее устройство в каждый момент находится в некотором состоянии q_j Î Q_, Q₌{q₀,q₁,q₂,...,q_r-1}. Множество Q называется внутренним алфавитом или множеством внутренних состояний. Иногда в Q выделяются подмножества Q₁ и Q₀ начальных и заключительных состояний соответственно. Предположим, что r>1, и в множестве состояний имеется одно начальное состояние q₁ и одно заключительное состояние q₀.

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

Работа управляющего устройства описывается тремя функциями:

G: Q´ A ® Q, F: Q ´ A ® A, D: Q ´ A ®{ R,L,S }.

Функция G называется функцией переходов, F-функцией выходов,D-функцией движения записывающей (считывающей головки). Функционирование алгоритмической модели можно задать списком пятерок вида:

(q_i,a_j, G(q_i,a_j ),F(q_i,a_j),D(q_i,a_j)). (2.1)

или короче (q_ia_jq_ija_ijd_ij). Эти пятерки называются командами.

В общем случае функции G, F, и D являются частичными, т.е. не для всякой пары вида (q_i,a_j) определена соответствующая пятерка вида (2.1). Список всех пятерок, определяющих работу машины Тьюринга, называется программой машины Тьюринга. Программу часто задают в виде таблицы, Табл. 13.

Если в программе для пары (q_i,a_j) пятерка вида (2.1) отсутствует, то в таблице на пересечении строки и столбца ставится прочерк.

 

Таблица 13Табличное задание программы машины Тьюринга

Q   A	q0	qi	qr-1
a0		. . .
aj	...	(qij,aij,dij)	...
an-1		. . .

Работу машины Тьюринга удобно описывать на языке конфигураций. Пусть в некоторый момент самая левая непустая ячейка c₁ содержит символ а_i1, а самая правая непустая ячейка c_s, s³2, содержит символ a_is (между ячейками c₁ и c_s находятся v ячеек). В этом случае говорят, что на ленте записано слово Р= (a_i1,a_i2,...,a_is), где a_ip - символ, содержащийся в этот момент в ячейке c_p, 1£ p £ s. При s=1, т.е. когда на ленте записан один непустой символ, Р=a. Пусть в этот момент управляющее устройство находится в состоянии q_i и головка обозревает пустую ячейку, расположенную слева или справа от слова Р, и между этой ячейкой и первой (соответственно последней) ячейкой слова Р расположено v пустых ячеек. Конфигурацией машины в этот момент является слово

Здесь L - пустой символ алфавита А.

Если в некоторый момент лента пуста, то конфигурацией машины будет слово q_i L.

Если в программе машины нет пятерки вида (2.1) для пары (q_i,a_j) или новое состояние является заключительным, то машина прекращает работу, а соответствующая конфигурация называется заключительной. Конфигурация, соответствующая началу работы машины, называется начальной.

Зоной работы машины Т на слове Р называется множество всех ячеек, которые за время работы машины хотя бы один раз обозреваются головкой.

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

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

Если в некоторый момент времени конфигурация машины была К, а в следующий момент К₁, то конфигурация К₁ называется непосредственно выводимой из конфигурации К, что обозначается как К ├ К₁. Если К₁ - начальная конфигурация, то последовательность К₁ ├ К₂ ├ …├ К_m, где любые две рядом расположенные конфигурации связаны отношением непосредственной выводимости при 1£i£m-1, называется тьюринговым вычислением. При этом говорят, что конфигурация К_m выводима из конфигурации К₁ и пишут К₁ ╟ К_m. Если К_m - заключительная конфигурация, то К_m заключительно выводима из К₁. Это записывают: К₁ ╞ К_m.

Пример. Выяснить, применима ли машина Т, заданная программой П, к слову Р. Если применима, то найти результат применения и заключительную конфигурацию. Принять, что пустой символ обозначается 0, q₁ - начальное состояние, q₀ - заключительное состояние.

П:	- обрабатываемое слово.

 

Последовательность конфигураций, проходимых машиной Т в процессе работы над словом Р, имеет вид:

q₁1³0²1² ├ 1q₁1²0²1² ├ 1²q₁10²1² ├ 1³q₁0²1² ├ 1³0q₂01² ├ 1³0²q₃1² ├

1³0²1q₂1 ├1³0²q₁1² ├1³0²1q₁1 ├ 1³0²1²q₁0 ├ 1³0²1²0q₂0 ├

1³0²1²0²q₃0 ├ 1³0²1²0²q₀0.

Машина Т применима к данному слову Р, и результат работы машины Т над словом имеет вид: Т(1³0²1²)=1³0²1².

Примеры

1. Разработать программу для перевода числа, записанного в унарной системе счисления, в двоичную систему счисления. Машина начинает работу над унарным словом, записанным на ленте, в состоянии q₁, а записывающая-считывающая головка обозревает крайний левый символ унарного слова. По окончании работы программы машина должна находиться в состоянии q₀,,а записывающая-считывающая головка обозревать крайний левый символ двоичного слова, записанного на ленте.

Число К в унарной системе счисления обозначается словом Q=(//…/), где символ «/» повторяется К раз.

В этой задаче А_вх={/}, А_вых = {0,1}, L - пустой символ. Построим программу П, решающую данную задачу. Рабочий алфавит машины Т - A={/,L,0,1}. Работу программы организуем циклически. Пусть к началу k -го цикла на ленте выписано слово PQ, где Р - двоичная запись уже считанной части числа К, Q - остаток унарного слова, Q =/^(n–k), т.е. последовательность (n-k) унарных символов. После выхода из этого цикла на ленте должно быть написано слово P`Q`, где Р` - -двоичная запись числа К+1, Q`- остаток унарного слова, равный /^(n–k-1). В течение k -го цикла из Q удаляется один унарный символ /, а к двоичной записи Р прибавляется 1 в двоичной системе счисления. При этом записывающая (считывающая) головка проходит слово PQ (непустое) слева направо, используя команды

q₁ 1 q1 R, q₁ q₁ R, q₁ /q₁ / R, q₁ Lq₂ L L.

Последняя команда «нащупала» конец слова и вернула головку на последнюю букву в состоянии q₂. Далее головка стирает эту букву, если это /, и запоминает необходимость прибавления 1 к двоичному числу Р при помощи команды q₂/ q₃LL.

Затем головка возвращается влево до начала двоичного слова Р, используя команду q₃/q₃/L и осуществляет двоичное прибавление 1 к слову Р в соответствии с правилами двоичного сложения. Это работа выполняется подпрограммой

q₃1q₃L; q₃q₄1L; q₄ 0 q₄ 0 L; q₄1q₄ 1 L; q₄Lq₁ L R; q₃Lq₁1 S.

После завершения работы по приведенному фрагменту программы сложение окончено, и записывающая-считывающая головка расположена над первой буквой слова Р. Осталось описать выход из цикла, когда все унарные символы стерты. В этом случае работают команды: q₂1q₀1 S; q₂ q S.

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

Таблица 14 Программа машины Тьюринга, выполняющей перевод числа из унарной системы счисления в двоичную систему счисления

Q A	q1	q2	q3	q4
/	q1 / R	q3 LL	q3 / L	-
	q1 1 R	q 01 S	q 30 L	q4 1 L
	q1 0 R	q0 0 S	q4 1 L	q4 0 L
L	q 2 LL	-	q1 1 S	q 1 LR

 

В качестве примера работы программы рассмотрим работу машины над словом P=(/////), содержащим пять унарных символов:

q ₁///// ├ ///// q₁ L ├ //// q ₂ / ├ /// q ₃ / L ├ q ₃ L//// ├ q₁1//// ├ 1 /// q₂ / ├

1// q₃ / L ├ q₃ 1 /// ├ ├ q₃L0/// ├ q₁10 /// ├ 10 // q₂ / ├ 10 / q₃ / L ├ 1q ₃ 0// ├ q₄11 // ├ q₄L11// ├ L q ₁11// ├ ├ 11| q₂ / ├ 11 q₃ / L ├ 1q₃ 1 / ├ q₃10 / ├

q₃ L 00/ ├ q₁100 / ├ 100q₂ / ├ 10q₃0 ├ 1q₄01 ├ q₄ 101 ├ q₄ L101 ├ L q₁101├ 10q₂1├ 10q₀ 1.

Результат применения машины Тьюринга, заданной предложенной программой, к записанному на ленте слову, состоящему из пяти унарных символов, равен 101₂=5₁₀. В формальной записи - Т(/////)= 101.

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

Рассмотрим алфавит Построим машину Тьюринга, удовлетворяющую следующему условию:

Пусть, например, m=5, n=3. Слово, записанное на ленте в начале работы машины, будет иметь вид

Λ/////+///Λ.

Записывающая-считывающая головка установлена над крайним левым символом слова, записанного на ленте, Управляющее устройство находится в начальном состоянии q₁. В конце работы машины над словом на ленте должно быть записано восемь унарных символов, управляющее устройство должно находиться в заключительном состоянии q₀, записывающая-считывающая головка должна обозревать крайний левый символ слова на ленте.

Программа, реализующая выполнение этих действий, может включать следующие шаги. Машина начинает работу в начальном состоянии q₁, подтверждает унарный символ /, содержащийся в обозреваемой ячейке, и, оставаясь в состоянии q₁, перемещается на одну ячейку вправо. При этом выполняется команда q₁/q₁/R. Дойдя до ячейки, в которую записан символ +, машина записывает в эту ячейку унарный символ, выполняя команду q₁+q₁/R, и затем продолжает движение вправо до тех пор, пока не «нащупает» конец слова, т.е. пустую ячейку (с символом Λ). К этому времени число унарных символов на ленте окажется на единицу больше суммарного числа исходных унарных символов. Поэтому один символ необходимо стереть. Для этого необходимо вернуть головку к ячейке, в которую записан последний унарный символ, выполнив команду q₁Λq₂ΛL. Новое состояние q₂ позволит стереть унарный символ в обозреваемой ячейке, выполнив команду q₂/q₃ΛL. Теперь на ленте записано нужное число унарных символов. Новое состояние q₃ предназначено для перемещения головки влево без изменения содержимого ячеек, команда q₃/q₃/L.

«Нащупав» конец слова слева, можно перейти в заключительное состояние q₀ с помощью команды q₃Λq₀ΛR. При этом головка окажется над крайней левой ячейкой записанного на ленте слова.

Программа машины Тьюринга может быть представлена табл.15.

Таблица 15 Программа машины Тьюринга, выполняющей сложение унарных чисел

	q1	q2	q3
/	/q1R	Λq3L	/q3L
+	/q1R	*	*
Λ	Λq2L	*	Λq0R

Последовательность конфигураций, проходимых машиной в работе над словом запишется следующим образом:

q₁/////+/// ├/q₁////+/// ├ //q₁///+/// ├ ///q₁//+/// ├ ////q₁/+/// ├

├ /////q₁+/// ├ //////q₁/// ├ ///////q₁// ├ ////////q₁/ ├ /////////q₁Λ ├

├ ////////q₂/ ├ ///////q₃ /Λ ├ //////q₃// ├ /////q₃/// ├ ////q₃////

├ ///q₃///// ├ //q₃////// ├ /q₃////// ├ q₃//////// ├ q₃Λ//////// ├ q₀////////.

Результатом работы машины над словом, записанным на ленте, является новое слово, содержащее восемь унарных символов. Записывающая - считывающая головка находится над крайней левой буквой заключительного слова. Управляющее устройство перешло в заключительное состояние q₀.

⇐ Предыдущая19202122232425262728Следующая ⇒

Поделиться:

Читайте также:

Теория милосердия» в подходах древнерусских книжников

Воспользуйтесь поиском по сайту: