Л.С. Корухова, М.Р. Шура-Бура - Введение в алгоритрмы, страница 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.