Языки и трансляции. Мартыненко Б.К. - 84 стр.

UptoLike

ВУЗ: 

СПбГУ | Санкт-Петербург

Составители: 

Рубрика: 

83
входными символами. Остальные ячейки до бесконечности содержат пробел —
специальный символ ленты, который не является входным символом.
Один такт машины Тьюринга, в зависимости от символа, сканируемого
головкой ленты, и состояния конечного управления,
1) изменяет состояние;
2) замещает (печатает) символ в сканируемой ячейке ленты символом ленты,
не являющийся пробелом;
3) сдвигает головку ленты влево, если возможно, или вправо на одну ячейку.
Определение 6.1. Машина Тьюринга (Tm Turing machine) является
формальной системой T =(Q, Σ, Γ, δ, q
0
, F), где Q — конечное множество
состояний; Γ — конечное множество допустимых символов ленты, причём
один из них, обычно обозначаемый буквой B, есть пробел; Σ ⊆ Γ \ {B} — мно-
жество входных символов; δ : Q ×Γ→Q × (Γ \{B}) × {L, R} — функция сле-
дующего такта (движения), которая для некоторых аргументов может быть не
определена
8
; q
0
∈Q — начальное состояние; F ⊆ Q — множество конечных
состояний.
Определение 6.2. Конфигурацией машины Тьюринга назовем тройку (q, α, i),
где q∈Q — текущее состояние машины Тьюринга; α∈ (Γ \{B})
*
— строка,
являющаяся непустой частью ленты; i — целое, определяющее позицию
головки ленты, отсчитываемую от левого конца ленты, i ≥ 1.
Заметим, что если головка ленты покидает ячейку, она должна напечатать
непустой символ в этой ячейке, так что лента всегда содержит непустой блок
символов (α — этот блок) с бесконечным числом пробелов справа от него.
Определим теперь один такт (движение) машины Тьюринга T.
Пусть (q, A
1
A
2
... A
n
, i) — некоторая её конфигурация, где 1 ≤ i ≤ n + 1.
Случай 1.
Если 1 ≤ i ≤ n и δ(q, A
i
)=(p, A, R), то
(q, A
1
A
2
... A
n
, i) (p, A
1
A
2
... A
i – 1
AA
i +1
... A
n
, i + 1),
т.е. T печатает символ A в i-й позиции и двигается вправо.
Случай 2. Если 2 ≤ i ≤ n и δ(q, A
i
)=(p, A, L), то
(q, A
1
A
2
... A
n
, i) (p, A
1
A
2
... A
i – 1
AA
i +1
... A
n
, i – 1),
т.е. T печатает символ A в i-й позиции и двигается влево, не сходя с левого
конца ленты
.
Случай 3. Если i = n +1, то головка сканирует пробел B.
а) Если при этом δ(q, B)=(p, A, R), то
(q, A
1
A
2
... A
n
, n + 1) (p, A
1
A
2
... A
n
A, n + 2).
б) Если при этом δ(q, B)=(p, A, L), то
(q, A
1
A
2
... A
n
, n + 1) (p, A
1
A
2
... A
n
A, n).
8
Мы не позволили Tm печатать пробел ради простоты определения конфигураций. Однако
Tm могла бы иметь другой символ
псевдопробел, который трактавался бы точно так же, как
пробел, за исключением того, его можно печатать. Разумеется, никакой дополнительной
мощности не появляется за счёт введения такого символа. При неформальном обсуждении мы
часто допускаем печать пробела, зная, что вместо него можно использовать другой, но
эквивалентный ему символ.
T
−
−
T
−
−
T
−
−
T
−
−

Страницы