(рис. 1).
Каждой клетке бесконечной в обе стороны ленты сопоставлена координата её. Отрезок из клеток, находящихся от клетки 
на расстоянии, не превосходящем r, назовем r-окрестностью клетки 
Будем считать, что задана нумерация клеток множества 
- слева направо, т. е. первая клетка отрезка – самая левая, последняя – самая правая.
Последовательность клеток "х1,...,хt,...., называется физически реализуемой автоматом со скоростью V, если каждая клетка в этой последовательности удалена от предыдущей клетки не более, чем на расстояние |х(t+1)-x(t)|<=V.
Весь период непериодического движения автомата будем называть, сознательным движением автомата.
Определим движение автомата как последовательность его выходных символов b(1),…b(i)…, где b(i) – целые числа. Выходные символы b(i) - принимающие неотрицательное значение будем для удобства обозначать символом А(i), а b(i) принимающие отрицательные значения - будем обозначать В(i)
Лемма 3.
Существует физически реализуемая траектория на полосе, которую не может реализовать автомат с красками.
Доказательство вспомогательных утверждений.
Лемма 1.
Существует автомат с краской, который обходит плоскость.
Построим автомат в явном виде:
Входные данные берутся с обзора R=1
A | Q | Ш | Ц |
NSWE |
| (↑,1) |
|
N |
| (→,2) |
|
NS |
| (↓,3) |
|
|
| (↓,4) |
|
|
| (←,4) |
|
|
| (←,1) |
|
NSW |
| (↑,1) |
|
N |
| (↑,1) |
|
N |
| (↑,2) |
|
N |
| (→,2) |
|
N |
| (→,2) |
|
N |
| (→,3) |
|
NS |
| (↓,3) |
|
|
| (↓,3) |
|
|
| (↓,4) |
|
|
| (↓,4) |
|
|
| (←,4) |
|
|
| (←,1) |
|
N |
| (↑,2) |
|
N |
| (→,3) |
|
WE
E
S
E
SWE
SW
W
W
WE
E
E
E
S
E
S
E
S
E
SW
W
W
E
Лемма 2: Существует такой автомат хищник с красками Wс(R, V) такой, что если Wс во время своего функционирования обнаруживает некоторую жертву U’ при некоторых начальных расположениях хищника и жертв, то Wс ловит жертву U’ при тех же начальных расположениях.
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 |
