Гипотетические машины

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

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

·         конечные автоматы и

·         магазинные машины.

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

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

Машина Тьюринга (короче, Т-машина) была предложена английским математиком Аланом Тьюрингом в 1936 г. как простая гипотетическая модель вычислительного устройства. Т-машина состоит из ленты для хранения знаков, головки для чтения/записи и устройства управления с конечным множеством управляющих состояний’•

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

Машина Тьюринга (ТМ) работает следующим образом. На каждом шаге работы ТМ читает знак из той ячейки на ленте, которая находится под головкой чтения/записи. В зависимости от текущего состояния управления в данную ячейку записывается некоторый знак, управление переходит в новое состояние и головка смещается на одну ячейку влево или вправо или же сохраняет свою позицию.
Таким образом, машина Тьюринга ТМ = (Т, S, r, s0) охватывает:

·        

конечное множество Т входных знаков (считается, что # Î Т), которые могут быть записаны на ленту;

·         конечное множество S состояний;

·         (конечную) функцию переходов и, соответственно, отношений:

·         r: S х (ТÈ {#})=. a(S х (Т È{#}) х (<,>,¯ )

·         начальное состояние s0 Î

S.

Знак < означает сдвиг головки на одну позицию влево, >- сдвиг на одну позицию вправо, а знак ¯ означает, что головка сохраняет свою позицию. Для заданного состояния S1 и прочитанного головкой знака t1

тройка

(s2, t2, z) e r(s1, t1)

обозначает возможный шаг вычислений. Этот шаг приводит к новому состоянию s2, новому содержимому t2 ячейки, находящейся под головкой, и сдвигу z головки по ленте. Если для ТМ справедливо

Для любых t Î TÈ{#}, s e S: r(s,t)£ 1

то ТМ называется детерминированной.

Пример (машина Тьюринга). Ищется машина Тьюринга ТМ = (Т, S, r, s0) с

Т = {О, L},

S = {,s0,s1,s2,si}

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

...# а1... аn, #...           ai Î {L, 0}

и головка к началу работы стоит над ячейкой, содержащей а„, то машина останавливается с содержимым ленты ...# L #..., если число знаков L в {a1, ..., аn} нечетно, и с содержимым ленты ...# О #... в противном случае; головка по окончании работы должна находиться над ячейкой, в которой находится знак-результат.

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

Функция переходов Т-машины может быть задана конечным автоматом, в котором ребро, ведущее от состояния s к состоянию s, существует и помечено через (Î, а,m), если ; (s , а,m) Î r(s,q).



Пример ( функция переходов ТМ как конечный автомат).

Вычисления Т-машины могут быть описаны через последовательность конфигураций. Конфигурация

Т-машины состоит из четверки

(s, l, а,k) Î S х (ТÈ{#})* х (ТÈ{#}) х (ТÈ {#})*,

где s - текущее состояние,

l- слово левее головки,

а - знак под головкой,

k- слово правее головки.

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

 (s, 1, а,k), (s, <#> .1, а,k)   и

(s, I, a, k .<#>)

эквивалентны.

Для конфигураций (s, 1, а,k) и (s, 1, а, k) Т-машины пишут

(s, 1, а,k) -> (s, 1, а,k), если

(s , х, z) е r(s, а)

Без ограничения общности здесь считается, что слова k и 1 не пустые. Этого  можно достичь путем добавления знака #. Вычисление

Т-машины есть конечная или бесконечная последовательность конфигураций Кi, для 0<i<n      или i е N:

Ко®K1® К2®¼

Конфигурация Кn называется терминальной,

если не существует такой конфигурации К, что имеет место

Кn ® К.

Конфигурация (s, 1, а, ,k) Т-машины терминальна точно тогда, когда . справедливо

r (s, а) =Æ.

Вычисление называется полным,

если оно конечно и его последняя конфигурация Кn терминальна или же оно является бесконечным.

Т-машины соответствуют алгоритмам и также могут быть представлены программами. Детерминированная Т-машина соответствует программе вида:

      S1:   if... fi

      Si:    if    aktuell(ti)    then put(ki1); move(zi1);

goto si1

elif aktuell(tn)    then рut(гin ); move(zin ); goto sin,

fi

              … 

Sm: … 

причем Sj, Sjj e S, tij, kij e T, zij e {«, », }.

Пусть булевское выражение aktuell(x) дает значение true только в том случае, когда под головкой находится знак х. Процедуры put и move соответствуют операциям над абстрактной структурой данных «Тьюринг-лента».

На концепцию ТМ может опереться понятие вычислимости. Частичная функция

f: T* à T*

называется тьюринг-вычислимой,

если существует такая машина Тьюринга ТМ, что для всех слов t е T* справедливы следующие высказывания:



(1)        Конечное, полное вычисление (s0, t, #, £) à…à(Se,Г, #, £)

существует точно тогда, когда функция f определена для t и справедливо

f(t) = k,    где k Î Т*.

(2)        Бесконечное вычисление

(s0, t, #, e) à...

существует точно тогда, когда функция f для аргумента t не определена.

Тьюринг-вычислимость может быть перенесена на частичные функции

f: N” à N

путем выбора конкретного представления чисел.

Ниже приводится ряд простых функций, которые являются Т-вычислимыми:

(1)        Константы. Отображения с: N” ->

N, для которых существует b Î N с c(x1, ..., xn) = b для всех x1, ..., xn Î N.

(2)        Функция следующего числа

succ: N àN,   где succ(n) = n+l.

(3)        Всюду определенная функция предыдущего числа

      pre: N ->    N, где

pre(n)=[ 0,         если n = 0; n-1  иначе].

(4)        Частично определенная функция предыдущего числа pred: N à N где pred(n)=[n—1, если n>0; не определено   иначе].

Это примеры для очень простых функций, которые являются Т-вычислимыми.

Более сложные примеры можно получить путем построения Т-машин из заданных. Например, можно построить последовательную композицию Т-машин: пусть TM1 и TM2 - машины Тьюринга с одинаковыми множествами входных знаков Т, с начальными состояниями соответственно s1 и s2,

и пусть множества их состояний S1 и S2 дизъюнктивны. Построить новую Т-машину ТМ0 с множеством входных знаков Т, начальным состоянием s1, множеством состояний s0=S1ÈS2 и функцией переходов r0,специфированрой следующим образом:

r0(s,t)=[r1(s,t),sÎS1Ùr1(s,t)¹Æ;{(s2,t,¯)},sÎS1Ùr1(s,t)=Æ;r2(s,t),sÎS2]

Последовательная композиция двух Т-машин соответствует вычислению, при котором сначала работает машина TM1 с исходным заданным словом, а когда она завершает свою работу, запускается машина ТМ2, которая использует слово на ленте, порожденное машиной TM1. Так построенная Т-машина вычисляет композицию функций, которые вычисляются Т-машинами.



Эта конструкция может быть обобщена. Для этой цели определяется общая композиция для частичных функций. Пусть

g: N” à N,

hi: N” à N, 1<i<n, являются частичными функциями. Тогда функция

      f: Nnà N;

описанная ниже, определена через композицию

функций h1, ..., hn и g. Примененяется функция f для всех аргументов (x1, ..., хm) следующим образом;

      f(x1,...,xm)=g(h1(x1,...,xm),...,hn(x1,…,xm)),

      если для всех i, 1 £ i £ m,

применение функции hi(x1, ...,xm) определено и также                определено применение функции g к аргументам

(h1(x1, ..., xm), ..., hn(x1, ...,xm)). Функция f для аргументов (x1,...,хm)  не определена, если

·         хотя бы для одного i, 1 £  i £ m, значение функции hi(xi, ..., xm) не определено или

·         для всех i, 1£ i £ m, применение функции hi(x1, ..., хm) определено, но применениефункции g к аргументам

(h1(x1, ..., xm), ..., hn(x1, ..., xm)) не определено.

Тогда для функции f  пишется выражение g.[h1,..., hnJ.

Фнкция f является тотальной (т. е. всюду определенной), если все функции h1, ..., hn и g тотальны (всюду определены).

С помощью обобщения только что описанного вида композиции ТМ получается следующая теорема.

Теорема (обобщенная композиция ТМ). Если

g: NnàN

hi: N’”à N,      где 1£ i£ n,

есть Т-вычислимые частичные функции, то функция

f: N’”à N,

определенная через композицию функций h1,..., hn и g:

f=g.[h1,..., hn],

также является Т-вычислимой функцией.

Эта теорема показывает, что множество Т-вычислимых функций замкнуто по отношению композиций функций. Композиция Т-вычислимых функций дает Т-вычислимую функцию.

Имеются и другие варианты машин Тьюринга, например:

·         машины с лентой, бесконечной только с одной стороны (и конечной лентой с другой стороны);

·         Т-машины со многими лентами.



Однако все они приводят к тому же самому понятию Т-вычислимой функции.

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

Регистровые машины

Регистровые машины (короче, R-машины) являются гипотетическими машинами, которые по своей структуре сильнее приближаются к употребительным в настоящее время ЭВМ. Рассматриваются R-машины с конечном числом регистров, однако с неограниченным их размером, чтобы регистры могли принимать сколь угодно большие натуральные числа.

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

(0) е есть программа (пустая программа);

(1)        succj есть программа (1£i£n);

(2)        predi есть программа (1£i£n);

(3)        если mi и M2 - программы, то M1; М2 также есть программа;

(4)        если М - программа, то while(M) также есть программа (1 £ i £n).

Множество программ для n-R-машины обозначим через n-PROG.

Конфигурация n-R-машины состоит из пары

- (s, р) е N” х n-PROG.

На множестве конфигураций специфицируется отношение переходов состояний —> следующими правилами:

(s, slicci) à ((s1, ..., si-i, si+l, si+i, ..., sn), e),

(s, predj,) -> ((s1, ..., sj-i, b, sj+1, ..., sn), e),

где

k=0, если si = 0, sj=0

si-l,sj-1 инач

Для конфигурации (s,e) следующая конфигурация не определена, поскольку E есть пустая программа.

Вычисление n-R-машины с исходной конкретизацией памяти s для программы р есть конечная или бесконечная последовательность конфигураций с c0 = (s, р) и для

i Î

N:

сi -> Ci+i.

Конфигурация с называется терминальной,

если не существует такой: конфигурации с

что сàc

Для терминальной конфигурации с =( s, р) всегда р = e

Вычисление называется полным,

если последовательность ко^фигура-1 ций бесконечна или же она конечна и последняя конфигурация сk терминальна. Тогда n-R-машина с программой р вычисляет выход (результат) s для входа s.

Наряду с n-R-машинами рассматриваются также R-машины с неограниченным числом регистров, а также R-машины с командами перехода. Регистровые машины соответствуют простой форме while-программ, состоящих из операторов присваивания, условных операторов, последовательной композиции операторов и while-циклов.


Содержание раздела

---

---