Конспект установочных лекций по комплексному курсу Информатика, Теория информации


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


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

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

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

(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* справедливы следующие высказывания:




Начало  Назад  Вперед



Книжный магазин