Въведение

Всичко започна през 1950 г., когато Джон фон Нойман си постави задачата да покаже, че е възможно съществуването на самовъзпроизвеждащи се автомати. С подходяща инструкция такава машина би построила точно копие на самата себе си. Всяка от двете машини ще направи след това още по една, четирите ше се превърнат в осем и т. н.

В доказателството на възможността да се построят такива машинина фон Нойман се използва това, което днес е известно под името “хомогенно клетъчно пространство”, еквивалентно на безкрайна шахматна дъска. Всяка клетка може да се намира в краен брой “състояния”, включително и в “покой” (казва се празно състояние); състоянието на клетката се влияе от краен брой “съседни” клетки. Състоянията се менят на дискретни стъпки във времето според “правилата на прехода”, които се прилагат едновременно към всяка клетка. Клетките символизират основните части на краен автомат, а конфигурацията от “живи” клетки е идеализиран модел на такава машина. Играта на Конуей се развива в точно такова пространство. Прилагайки правилата на прехода към пространство, всяка клетка на което се намира в едно от 29 състояния и има четири съседа, фон Нойман доказал съществуването на конфигурация с около 200 000 клетки, която може успешно да се самовъзпроизвежда.

Основни свойства на клетъчния автомат (СА)

Клетъчният автомат има следните атрибути:

Пространството, модел на света, е сбор от клетки	Едномерно-развива се в един ред, обикновено с последователни генерации, представени една под друга
	Двумерно	пример е играта “Живот”
Времето върви с дискретни стъпки (t=1,2…)
Областта (nbhd) на клетката. Тези клетки, чието състояние влияе на следващото състояние на текущата клетка.	Едномерна, N=3
	Едномерна, N=5
	Двумерна, по фон Нойман, N=5
	Двумерна, по Мур, N=9
Приемат се краен брой състояния на клетката според нивото на детайлност, до което искаме да стигнем разглеждайки клетката. Броя състояния се означава с S. Разглеждаме обикновено двоични (S = 2) СА, със състояния: живи (черни) или мъртви (бели) клетки. Фон Нойман работил с S = 29 за самовъзпроизвеждащ се СА. Ако броя състояния за клетка е S и броя клетки, създаващи областта е N, то имаме SN, комбинации на клетки в областта N.			За едномерна област, N=3 и бинарно състояние имаме 23=6 , комбинации на клетки. Но например за играта “Живот” комбинациите са SN=29=512!
Определят се правила, при които всяка клетка за всяка стъпка изчислява своето ново състояние по състоянието на съседите й в nbhd. Правилата определят точно кое от S-възможните состояния ще бъде резултат от всяка от SN конфигурации за областта N или ще имаме S(SN) възможни правила.За двумерна област по Мур възможните правила са 2(29) = 2512=13 407! Правилата за въртящия се GIF горе (пример за едномерна област, N=3 ) са: ако всичките три клетки са бели, новото състояние на клетката ще е бяло. ако всичките три клетки са черни, новото състояние на клетката пак ще е бяло във всеки друг случай, новото състояние на клетката ще е черно.

Клетъчните автомати се използват при съставяне на модели в медицината, за химически, биологически и обществени взаимодействия.

За много от тези приложения, точните позиции на живите клетки не са важни, е важно само количеството на живите клетки. Такива клетъчни автомати се наричат тотални.

Чувствителност към началните условия

Интересни резултати се получават при произволно начално положение на живи и мъртви клетки? Ето например как би изглеждал най-горния пример:		А може ли някой да обясни удивителната прилика с шарките на раковината Конус?

Чувствителността към началните условия е част от определението за детерминиран хаос. Разлика дори и от една клетка дава големи различия впоследствие при едни, но при други те се заличават.

Видове поведение

Стивън Волфрам (Stephen Wolfram)-детето-чудо на британската математика е определил четири класа поведения на СА за случаи с начално произволно разпределение на живи и мъртви клетки.

Клас I: – Изцяло хомогенен, всички сметка умират (или всички живеят), предшествани от краткотрайно движение
Клас II: Периодичен – след някои начални краткотрайни поведения, започва да се повтаря, в пространството (хоризонтално), или във времето (вертикално), или в двете.
Клас III: Хаотичен – растат хаотично с краткотрайни острови на реда и са много чувствителни към началните условия.
Клас IV: Сложен – растат по сложен начин както с локално стабилно поведение (изпълняват ролята на памет) така и перспективни корелации (пренасящи данни). Първият модел е с шахматен фон – памет; вторият е с фон вертикални линии.
Клас IV е най-интересен и най-рядък. При двудименсиалната игра на Конуейот IV клас са: от първия тип са блоковете (памет) от втория тип са глайдерите (пренасяне на данни)

Генетичните алгоритми и изкуственият живот

Изкуственият живот (или A-life) е анализ на поведението на естествените живи системи, самоорганизацията, адаптацията , еволюцията, метаболизма…. Това са търсения да се обясни живота във всички свои прояви, без ограничения. Окончателната цел е да се извлече логическата форма на живите системи.

При търсенето на алгоритъма на генетичния код като основно свойство се определя устойчивостта на грешки; живите системи са ефективни, защото умеят да се приспособяват в широк спектър среди. Като се извлече алгоритъма на избора при естествената адаптация и се въведе в изкуствената форма, може да се достигне аналогична широта на изпълнение.

Съставянето на генетичните алгоритми има седем стъпки. (система на класифициране, приспособяване, преход и мутация)

1. Да се изрази решението като последователност от алтернативни въпроси (система на класифициране на проблема).

Правилата за СА могат да се представят като низ от отговори на въпроса “тази конфигурация дава ли жива клетка?

2. Да се започне с произволно начално разпределение

3. Да се провери всяко предлагано решение.

Представя се графично като пространствена релефна карта на приспособяването на генотипа. При откриване на най-подходящото решение, се премества в генотипното пространство по посока на нарастването на пригодността, изменяйки гена с времето.

4. Пригодността на всяко предлагано решения се проверява.

5. Отстраняват се най-неподходящите членове на популацията.

6. Награждават се най-подходящите като им се позволи да се възпроизведат със случайни мутации. Прилагат се генетични алгоритми и клетъчни автомати.

7. Повтарят се точки 3-6 в новата генерация.