Составители:
Рубрика:
символов, а алфавит состояний головки - r символов, то для
сложности вычислений справедливы оценки:
s
(σ) ≤ |
σ
|+t (
σ
),
M M
()
(
)
(
)
σ
σσ
M
s
MM
krst
2
≤
,
где |σ| - длина цепочки σ.
Доказательство [14].
1. В начальной ситуации на ленте записана цепочка
σ
,
занимающая |σ| ячеек. На каждом шаге вычислений добавляется
не более одной активной ячейки, поэтому s
(
σ
) ≤ |
σ
|+t (
σ
).
M M
2. Выполним подсчет числа всевозможных конфигураций
(i-1) (i) (s′)(1)
K=a
…a q
j
a …a (s′ ≤ s)
с длиной активной зоны, не превышающей s. Имеется
вариантов записи символов на ленте, r вариантов
состояния и s′
ss
kk ≤
′
≤ s вариантов положения головки, а также s
вариантов длины s′ конфигурации K. Поэтому общее число
конфигураций не превосходит rs
2 s
k . Повторение конфигураций
возможно только в случае зацикливания машины. Следовательно,
для числа тактов можно записать
(
)
(
)
()
σ
σσ
M
s
MM
krst
2
≤
.
Теорема доказана.
Частный случай – машина, вычисляющая характеристическую
функцию множества L
*
: ⊆Σ
M
: Σ*→{0,1}.
μ
M
называется языком, распознаваемым машиной M:
Множество L
M
*
L
={
σ
⏐
σ
∈Σ ,
μ
(
σ
)=1}.
M
: N→N:
Временнáя сложность вычисления T
M
()
⎪
⎭
⎪
⎬
⎫
⎪
⎩
⎪
⎨
⎧
=Σ∈
=
∗
шагов требует входом со вычисление
что , , цепочка такаясуществует
max
m
n
mnT
M
σ
σσ
.
169
Страницы
- « первая
- ‹ предыдущая
- …
- 83
- 84
- 85
- 86
- 87
- …
- следующая ›
- последняя »
