10 / 13
Опишем намеченную процедуру подробно. Для каждого автома-
та
G
s
указанное слово
α
=
α
(1)
α
(2)
. . .
дает путь
a
s
(1)
→
a
s
(2)
→
. . .
Обозначим через
D
s
множество натуральных чисел
i
, для которых
ребро
a
s
(
i
)
→
a
s
(
i
+ 1)
лежит в множестве
Q
0
s
.
Известно, если
i
∈
D
s
,
то в момент
i
автомат
G
s
выдает прогноз
β
s
(
i
)
; если
i /
∈
D
s
, то
в момент
i
автомат не дает никакого прогноза. Введем функцию
k
7
→
Φ(
k
)
, k
= 1
,
2
, . . .
, по следующему правилу: для каждого
k
рас-
смотрим такие
s
, для которых числа
k, k
−
1
, . . . , k
−
R
входят в
множество
D
s
. Другими словами, выбираются те автоматы, которые
давали прогноз от момента
k
−
R
до момента
k
. Наименьший из таких
номеров
s
обозначим через
Φ(
k
)
. Итак, равенство
Φ(
k
) =
i
означает
следующее: во-первых, множество чисел
{
k
−
R, . . . , k
}
содержится в
множестве
D
i
, во-вторых, указанное множество чисел не содержится
в множестве
D
i
0
при
i
0
< i
. Функция
Φ
построена. Отметим ее свой-
ство, которое следует из ее определения и будет использовано далее:
если для некоторого
i
числа
{
k
−
R, . . . , k
}
входят в множество
D
i
,
то
Φ(
k
)
≤
i
. Наконец, взяв автомат с найденным номером
i
= Φ(
k
)
,
возьмем выданный им (в момент
k
) прогноз
β
i
(
k
)
. В результате для
угадывания слова
α
=
α
(1)
α
(2)
. . .
получили цепочку прогнозов
β
(
k
) =
g
i
(
k
)
, k
= 1
,
2
, . . . , i
= Φ(
k
)
.
(4)
В цепочке (4) возможны пропуски (отмечаем их черточками), так как
для некоторых
k
величина
Φ(
k
)
может быть не определена. Образно
говоря, в каждый момент времени
k
каждый
m
-й автомат пытается
угадать символ
α
(
k
+ 1)
нашего слова; но из всех прогнозов отбира-
ется прогоз, выданный автоматом с наименьшим номером, который
угадывал (возможно, не всегда удачно) в моменты времени от
k
−
R
до
k
(без прерываний).
Теорема 2.
1. Функция
k
→
Φ(
k
)
определена при
k > k
0
,
где
k
0
—
постоянная
,
зависящая от
α
. 2. Пусть число
R
выбрано так
,
что
R >
4
mT
i
для всех
i
= 1
, . . . , m
.
Тогда последовательность (4) дает
процесс частичного угадывания с интервалом угадывания
R
.
J
Докажем первое утверждение теоремы. По условию
α
∈
L
s
=
=
L
(
q
0
s
, Q
s
, Q
0
s
)
для некоторого
s
. Поскольку
lim
α
=
Q
0
s
, соответству-
ющий путь в орграфе
G
s
полностью лежит в
Q
0
s
, начиная с некоторого
момента
k
0
. Следовательно, числа
k, k
−
1
, . . . , k
−
R
принадлежат мно-
жеству
Q
0
s
для всех
k > k
0
, если число
k
0
достаточно велико. Поэтому
функция определена при
k > k
0
.
Доказательство второго утверждения теоремы 2 требует некоторых
приготовлений. Число
k > k
0
назовем точкой скачка функции
Φ
при
Φ(
k
)
6
= Φ(
k
+ 1)
.
Лемма 6.
В любом отрезке длиной
R
имеется не более
2
m
точек
скачка.
12
ISSN 1812-3368. Вестник МГТУ им. Н.Э. Баумана. Сер. “Естественные науки”. 2016. № 2