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

Таким образом, машина Тьюринга ТМ = (Т, 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).

Содержание  Назад  Вперед