Л.С. Корухова, М.Р. Шура-Бура. Введение в алгоритмы (793777), страница 5
Текст из файла (страница 5)
Здесь Q' = Q \ { q s}, т.е. Q без состоянияостанова.Таким образом, все поведение автомата можно описать тремя функциями - φ , ψ и δ,которые удобно изобразить тремя таблицами вида:Сост.\симв.Λq0a1…aj…..ЗНА-q1ЧЕНИЯ….ФУНК-qsЦИИφψapδТаблицы для приведенных выше трех функций можно "слить" в одну, которую можносчитать описанием соответствующей машины Тьюринга:Сост.\симв.q0q1…qi….qsΛa1…aj…apa j',X,q i'где a j'∈ Ã, q i'∈ Q, X = { R, L}15Эта таблица обычно называется таблицей переходов.
Строка таблицы,соответствующая состоянию q s, фактически состоит из пустых клеток, и ее можноисключить. Однако при рассмотрении композиции алгоритмов наличие этой строкиупростит понимание того, как строится таблица переходов для композиции. Работамашины Тьюринга оказывается процессом выполнения весьма простого алгоритма,использующего таблицу переходов в соответствии с описанными выше правилами. Нарезультат работы машины Тьюринга может влиять начальное расположение управляющейголовки относительно изображения исходного слова на ленте.
Исключить этунеопределенность можно, введя дополнительное соглашение. Например, можно считать,что управляющая головка в начале работы обозревает клетку, расположенную левееисходного слова или клетку, в которой записан первый символ слова. В конце работыуправляющая головка "указывает" на первый символом слова-результата и находится всостоянии останова q s.Свяжем с машиной Тьюринга отображениеA*А*на множестве слов внешнего алфавита и будем говорить, что машина Т реализует этоотображение. Более того, мы будем считать, что эта машина реализует отображениеВ*A* ,где В ⊂ А и T'(w) = T(w), если w ∈ B*.
Такая ситуация возникает, если машина Тпереводит слова из В* только в слова из В*, хотя в процессе работы машины на лентумогли записываться при этом и символы из А \ В.Если забыть о неограниченности ленты машины Тьюринга, то такая машина выглядитв наше время вполне реальной. Все мы знаем о существовании машин - автоматов,способных выполнять куда более сложные последовательности операций, чем те, которыедолжны выполнять машины Тьюринга. Более того, чтобы понять, как можносконструировать машину Тьюринга, достаточно знакомства с элементарными сведениямииз электротехники. Однако препятствием к полной реализации машины Тьюрингаявляется предположение о неограниченности ленты.
Напомним, однако, что, если мыжелаем использовать машину Тьюринга для реализации алгоритмов, то предположение онеограниченности ленты весьма существенно из-за бесконечности множества A* всехслов в алфавите А и необходимости задания для начала работы машины сколь угоднодлинных слов изображающих исходные данные. Так, например, в случае алгоритмаЕвклида надо обеспечить задание пары сколь угодно больших чисел.Оставляя в стороне вопросы материальной реализации машин Тьюринга, подпостроением такой машины мы будем понимать выбор ее внешнего и внутреннегоалфавитов и задание таблицы переходов.Тьюрингом была высказана гипотеза о возможности реализации любого порожденногоалгоритмом отображения на множестве слов конечного алфавита при помощиподходящего предложенного им автомата, т. е.
машины Тьюринга. Эта гипотезанедоказуема, поскольку употребляемое в ней понятие алгоритма четко не определено. Ноее можно обосновать построением машин, реализующих конкретные алгоритмы.Говоря о гипотезе Тьюринга, как о возможности реализации любого алгоритма припомощи машины, подразумевают существование машины, реализующей алгоритм,эквивалентный данному.ПРИМЕР16Построим машину Тьюринга (МТ), которая к числу, записанному на ленте, прибавляет1.
Число задается последовательностью десятичных цифр, т.е. словом в алфавите А = {0,1, ..., 9 }. Пусть Λ обозначает пустую ячейку ленты.q 0 - начальное состояние МТ - поиск первой (левой) цифры числа;q s - состояние останова;q 1 - "ищем" последнюю цифру числа;q 2 - прибавляем 1 к цифре, записанной в обозреваемой клеткеq 3 - возвращаемся к первому (самому левому) символу слова-результатаСост.\симв.q0q1q2q3ΛΛ,R,q0Λ,L,q21,L,qsΛ,R,qs00,R,q10,R,q11,L,q30,L,q311,R,q11,R,q12,L,q31,L,q32…2,R,q12,R,q13,L,q32,L,q388,R,q18,R,q19,L,q38,L,q399,R,q19,R,q10,L,q29,L,q3Для того, чтобы эта машина выполняла прибавление 1, управляющая головка в началеработы должна находиться перед клеткой ленты, в которой записана цифра числа, либоперед клеткой левее заданного числа.5.1.1.
ОБОСНОВАНИЕ ГИПОТЕЗЫ ТЬЮРИНГАПравдоподобность гипотезы Тьюринга подтверждается не только возможностьюпостроения машин, реализующих конкретные алгоритмы, но и доказательствомвозможности построения машин, реализующих различные композиции алгоритмов, приналичии машин, реализующих алгоритмы - компоненты рассматриваемых композиций.Прежде всего отметим возможность рассмотрения лишь какого-либо одногоконкретного внешнего алфавита А, вспомнив об эквивалентности различных алфавитов.Кроме того, полезно ограничиться машинами Тьюринга, управляющая головка которых всостоянии останова всегда оказывается перед ячейкой ленты, в которой записан первыйсимвол слова-результата (как в примере выше).Пусть алгоритм D является произведением алгоритмов В и С (обозначается как D=B*Cили D=C(B) ).
Иначе говоря, слово-результат алгоритма D для исходного слова w являетсярезультатом применения алгоритма С к слову-результату алгоритма В для исходногослова w, т. е.D(w)=C(B(w))В предположении существования машин Тьюринга Т B и ТC, реализующих,соответственно, алгоритмы В и С, построим машину Тьюринга ТD, реализующуюалгоритм D.Пусть { q0B, q 1B, ..., q r B, q sB } - внутренний алфавит машины Т B и{q 0C, q 1C, ..., qtC, qsC} внутренний алфавит машины ТC. Внутренним алфавитом машины ТD выберем { q0B, q1B, ...,qrB, q0C, q1C, ..., qtC, qsC }, т.е.
объединение внутренних алфавитов машин ТBи ТC сисключением заключительного состояния машины ТB (qsB). Таблицу переходов машины ТDсоставим из всех строк таблиц переходов машин Т Bи ТC, в клетках которых всюду qsBзаменим на q0C, удалив, кроме того, строку, соответствующую состоянию q sB . Впрочемэто удаление носит лишь"косметический" характер, так как после проделанных замен q sBна q0C в состояние qsB управляющая головка построенной машины ТD никогда непереходит. Легко убедиться, что построенная машина реализует алгоритм D = B*C.17Покажем, как построить машину Тьюринга, реализующую альтернативу выполненияалгоритмов В или С в зависимости от истинности вычислимого предиката Р, еслипостроены машины Тьюринга ТB, ТC, ТP, реализующие соответствующие алгоритмы.Предположим, что внешние алфавиты всех трех машин совпадают, а относительномашины ТP предположим, что результатом ее работы для исходного слова w будетприписывание к этому слову w в его начало некоторого, выделенного для обозначенияистинности предиката, символа внешнего алфавита или любого другого символа, еслизначение предиката ложь.Сохранив внешний алфавит, внутренним алфавитом реализующей альтернативумашины Тьюринга ТAL возьмем объединение внутренних алфавитов машин Т B, ТC и ТP.Символом начального состояния машины ТAL объявим символ начального состояниямашины ТP, а символы конечных состояний машин Т B и ТC отождествим, объявив ихсимволом конечного состояния машины ТAL.
Таблицу переходов машины ТAL составим извсех строк таблиц переходов машин ТB, ТC и ТP, внеся в эти строки следующие изменения:в строке, соответствующей символу qsP, т.е. конечному состоянию машины ТP, во всеклетки, за исключением клетки из столбца, соответствующего символу, выделенному дляобозначения истинности предиката Р, впишем тройку (Λ,R, q0C), а в исключенную клеткудля символа "ложь"запишем тройку (Λ,R, q0B). Построенная машина ТAL, как нетрудноубедиться, реализует требуемую альтернативу.Существование машин Тьюринга, реализующих различные композиции алгоритмов,является серьезным доводом в пользу истинности гипотезы Тьюринга, хотя и не приводитк формальному доказательству ее истинности. Другим подтверждением гипотезыТьюринга можно считать строгие доказательства ее эквивалентности гипотезам,положенным в основу других подходов к формализации понятия алгоритма, - как тезисуЧерча о вычислимых функциях, так и принципу нормализации в рассмотренных ниженормальных алгоритмах Маркова.5.2.
НОРМАЛЬНЫЕ АЛГОРИТМЫ МАРКОВАВ 1954 году русский математик А.А.Марков предложил новый подход к формализациипонятия алгоритма. В отличие от подхода Тьюринга, доводящего простоту описываемыхопераций до замены символов, А.А.Марков предложил использовать замену слов,включив в шаг алгоритма процедуру выбора реализуемой замены.Для дальнейшего изложения нам потребуется знакомство с некоторыми терминами ипонятиями, играющими заметную роль не только в теории алгоритмов.Пусть А = { a 1 , a 2 , ... , a p } - конечный алфавит.Пусть u = a i1 ...aik и v = a j1...ajl - слова из A*.
Говорят, что слово w = a i1... aik aj1...ajlполучено конкатенацией (сцеплением) слов u и v (обозначается uv),а также, что слово wявляется конкатенацией этих слов. Очевидным образом конкатенация обобщается наслучай, когда u или v оказываются пустыми словами. Операция конкатенацииассоциативна. Следовательно, однозначно определяется конкатенацияuvw = (uv)w = u(vw) и конкатенация u1u2...u m.Говорят, что имеет место вхождение слова v в слово w, если w = u1vu2. При этом словаu1 и u2 называются, соответственно, левым и правым контекстом вхождения. Вхожденияслова v в w могут различаться контекстами. Среди таких вхождений вхождение сминимальной длиной левого контекста называется левым или первым вхождением v в w.Замена в слове w = u1vu2 слова v на слово v', т.е.
получение слова w' = u1v'u2,называется подстановкой, определяемой парой (v, v'). Пара (v, v''), определяющая18операцию подстановки называется формулой или правилом подстановки и длянаглядности часто изображается в виде:v v'Как v, так и v', могут быть пустыми словами. Формула подстановки v v' применима кслову w, если имеет место вхождение слова v в w. Подстановка с пустым левым словомвсегда применима.Алгоритм, названный А.А.Марковым нормальным, сводится к ряду подстановок,определяемых заданием конечной последовательности определяющих формулподстановкиv1 v'1.....v m v'm ,некоторые из них заранее выделены, как играющие особую роль в завершении алгоритма.Выделенные формулы подстановки называются заключительными и обычно отмечаютсядополнительным значком при стрелке , например: или * .В нормальных алгоритмах всегда идет речь о подстановках, связанных с заменойпервого вхождения левого слова формулы подстановки.
В процессе выполнениянормального алгоритма исходное слово преобразуется применением заданных формулподстановки. На каждом шаге исполнения нормального алгоритма либо осуществляетсяодна из заданных подстановок (а именно - первая применимая подстановка), либоалгоритм завершается, если ни одна из этих подстановок неприменима. Алгоритмзавершается и в случае выполнения на очередном шаге одной из заключительныхподстановок. Слово, полученное в результате последней из выполненных подстановок,считается результатом работы алгоритма.Описанные алгоритмы, в которых, как исходные слова, так и слова в подстановках,принадлежат A*, называются нормальными алгоритмами в алфавите А.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
