Научная литература
booksshare.net -> Добавить материал -> Биология -> Эбилинг В. -> "Физика процессов эволюции" -> 62

Физика процессов эволюции - Эбилинг В.

Эбилинг В., Энгель А., Файстель Р. Физика процессов эволюции — М.: УРСС, 2001. — 342 c.
Скачать (прямая ссылка): fizikaprocessovevolucii2001.djvu
Предыдущая << 1 .. 56 57 58 59 60 61 < 62 > 63 64 65 66 67 68 .. 176 >> Следующая

3. Рождение. Свободная (пустая) клетка превращается в занятую, если число соседних занятых клеток равно трем.
В ходе игры Конуэя на доске возникают весьма замысловатые и оригинальные конфигурации, которые легко моделируются на компьютере. Игра Конуэя позволяет моделировать значительную часть таких свойств биологических систем, как рост, гибель и взаимодействие (Eigen, Winkler, 1975, 1979).
Автомат фон Неймана, о котором пойдет речь, устроен гораздо сложнее. Он предназначен для того, чтобы сделать доступными математическому анализу процессы самовоспроизведения и эволюции. Речь идет о попытке найти ответы на следующие пять основных вопросов.
1. Логическая универсальность.
а) При каких условиях определенный класс автоматов логически универсален?
б) Существует ли логически универсальный автомат?
ии ИИ ИИ ИИ ИИ
* ИИ ии ИИ ИИ

* * и
* иии и иии и
* * и

к
и и И и и и
X* * ИИ и и ж и
и * и ж ж иии
ж
Конечный автомат с неограниченно продолжаемой лентой называется автоматом, или машиной, Тьюринга. Тьюринг показал, что предложенный им класс автоматов логически универсален, т. е. автоматы Тьюринга могут выполнить произвольный логический процесс (произвольное вычисление), если их снабдить конечным, но сколь угодно продолжаемым запоминающим механизмом (памятью). Тьюринг показал также, что существует универсальная машина Тьюринга, способная выполнять любые вычисления.
Тем самым Тьюринг дал положительный ответ на вопрос о логической универсальности, и фон Нейман поставил поэтому следующий вопрос.
2. Конструируемость.
а) Может ли один автомат быть построен другим автоматом?
б) Какой класс автоматов может быть построен каким-то автоматом?
3. Конструктивная универсальность.
а) Существует ли конструктивно универсальный автомат (т. е. автомат, способный построить любой автомат)?
4. Самовоспроизведение.
а) Существует ли самовоспроиэводящийся автомат?
б) Существует ли автомат, который помимо самовоспроизведения может решать и другие задачи?
5. Эволюция.
а) Может ли при конструировании автомата автоматом происходить усложнение типа автомата?
б) Может ли такая эволюция происходить в направлении от менее эффективного к более эффективному автомату (при надлежащем определении понятия эффективности)?
На все эти вопросы фон Нейман дал положительные ответы с помощью доказательства существования, построив специальный автомат, обладавший требуемыми свойствами. Фон Нейман воспользовался клеточным автоматом, у которого каждая клетка может находиться в 29 состояниях. Клеточный автомат состоит из многих однотипных автоматов, расположенных в узлах решетки; выход каждого автомата служит входом для соседних клеток. Нумерует клетки «радиус-вектор» (или вектор положения)
0 = (*> j)I *> 3 = 0, ±1, ±2,...
(5.51)
Рис. 5.10. Нумерация клеток клеточного автомвта
(рис. 5.10).
Ближайшими соседями клетки (г, j) по определению считаются клетки (i ± 1, j) и (г, j ± I), а ближними соседями — клетки (i ± l,j ± 1) (рис. 5.11).
В соответствии с этими определениями определим восемь различных векторов расстояния (рис. 5.12):

О 4 о
* X
о о

(о] ближние соседи ЕЯ ближайшие соседи
Рис. 5.11. Соседние (по определению) клетки
V = (1, 1),
5.3. Самовоспроизводящиеся автоматы V1 = (0,1),
(п -П.
(5.52)
v° = (1,0),
V2 — —V0 = (—1, 0), V3 = -D1 = (0, -1),
V6 = —V4 = (—1, —1), V = —V5 - (1, —1).
Тогда $ + »“ (а = 0,..., 3) — ближайшие, + (а =
4, ¦ • •, 7) — ближние соседи.
Время дискретно, т. е. изменяется по тактам:
t = 0,±l, ±2,
Рис. 5.12. Векторы разностей для обозначения (5.53) соседей
Изменяются состояния по правилу перехода F, одинаковому для всех клеток (внутренняя однородность):
п^а | а - 0,..., 3).
на каждом такте каждая клетка д находится в одном из п состояний п — 0,1,..., If - 1, т. е. состояние на такте t есть
(5.54) : (вну-
(5-55),
В некоторых клеточных автоматах, например, в игре Конуэя «Жизнь» (Eigen, Winkler, 1975), F зависит еще и от ближних соседей, т. е. индекс а пробегает значения
от 0 до 7.
В соотношении (5.55) F зависит от пяти переменных, которые могут принимать Ж значений, а поскольку F также принимает N различных значений при каждом значении аргумента,, всего существует
m = Nn> (5.56)
различных передаточных функций F (различных моделей).
Автомат фон Неймана имеет N = 29 различных состояний (в игре Конуэя только 2):
Предыдущая << 1 .. 56 57 58 59 60 61 < 62 > 63 64 65 66 67 68 .. 176 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed