Конспект установочных лекций по комплексному курсу Информатика, Теория информации
Гипотетические машины - часть 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} нечетно, и с содержимым ленты ...# О #... в противном случае; головка по окончании работы должна находиться над ячейкой, в которой находится знак-результат.
Эта Т-машина детерминированна, поскольку всегда существует единственное следующее состояние.
