Доказательство: Рассмотрим автомат хищник с красками Wс (R, V). Положим что, при таком функционировании автомат Wс обнаруживает некоторую жертву U при некоторых начальных расположениях.
Для обнаружения возможны следующие варианты:
1. В момент τ-1 жертва находится в зоне обзора, а в момент τ уже покинула её.
2. В момент τ-1 жертвы нет в зоне обзора, а в момент τ она попадает в неё.
3. В моменты τ-1 и τ жертва находится в зоне обзора.
Преследование жертвы будет происходить следующим образом: в случае 1 хищник, обнаруживший жертву, будет двигаться к той клетке, в которой жертва находилась в момент τ-1, в случаях 2 и 3 – к той клетке, в которой жертва находится в момент τ. Причем, если несколько жертв находятся в зоне обзора хищника, он выбирает для преследования любую из них (U’). За каждый такт хищник делает шаг с максимальной скоростью. Пусть (x, y) - координаты клетки, к которой в данный такт движется хищник. Тогда хищник делает шаг
(signx*V, 0) , если |x|≥V
(x, signy*(V-|x|)) , иначе.
Докажем, что при таком движении хищник через конечное число тактов поймает жертву. Пусть автоматы Wс и U’ в момент времени τ находятся в клетках с координатами (xW, yW) и (xU’,yU’) соответственно. Расстояние между автоматами ρτ в момент τ будем измерять по манхэттенской метрике.
В момент обнаружения τ жертвы U’(R’,V’) автоматом Wс ρτ ≤ R. Поскольку V’<V, то ρτ+2 ≤ ρτ - (V-V’) < ρτ
Таким образом, расстояние между хищником и жертвой уменьшается. Причем, если жертва движется с максимальной скоростью, то расстояние между хищником и жертвой за каждый такт уменьшается на 1. Следовательно, для того, чтобы поймать жертву, хищнику требуется не более R-V тактов. Лемма доказана.
Доказательство основных результатов
Теорема 1:
1)Существует 1 автомат с одним состоянием и с одной краской Wc (1,1), который обходит 
.
Доказательство:
Построим автоматы в явном виде:
1)
A | Q | Ψ | Φ |
NSWE |
| (↑, 1) |
|
N |
| (→,1) |
|
NS |
| (↓,1) |
|
|
| (↓,1) |
|
|
| (←,1) |
|
|
| (←,1) |
|
NSW |
| (↑,1) |
|
N |
| (↑,1) |
|
N |
| (→,1) |
|
WE
E
S
W
E2) Обход 
.
Будем обозначать «_» борт.
A | Q | Ψ | Φ |
NSWE |
| (↓, ) |
|
N_WE |
| (→,1) |
|
N_ |
| (↑,1) |
|
N |
| (←,1) |
|
N |
| (←,1) |
|
NSW |
| (↓,1) |
|
|
| (←,1) |
|
N_W |
| (↑,1) |
|
N |
| (↑,1) |
|
N |
| (→,1) |
|
N |
| (→,1) |
|
NS |
| (↓,1) |
|
|
| (↓,1) |
|
|
| (→,1) |
|
N |
| (↑,1) |
|
|
| (↓,1) |
|
E
_W
E3) Обход 
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 |
