Доказательство: Рассмотрим автомат хищник с красками 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), который обходит 
.
Доказательство:
Построим автоматы в явном виде:
A | Q | Ш | Ц |
NSWE |
| (↑, 1) |
|
N |
| (→,1) |
|
NS |
| (↓,1) |
|
|
| (↓,1) |
|
|
| (←,1) |
|
|
| (←,1) |
|
NSW |
| (↑,1) |
|
N |
| (↑,1) |
|
N |
| (→,1) |
|
WE
E
S
E
SWE
SW
W
E
Обход
. Будем обозначать «_» борт.
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
WE
W
_W
W
WE
E
E
S
E
_W
E
SW
3) Обход 
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 |
