Клітинний автомат
Матеріал з Вікіпедії — вільної енциклопедії.
Кліти́нний автома́т — сукупність, до якої входять:
- Набір клітинок, які утворюють періодичну решітку
- Задані правила переходу, що визначають стан клітини за теперішнім станом самої клітинки та тих її сусідів, що знаходяться від неї на певній відстані, яка не перевищує максимальну.
У якості ґратки зазвичай беруть розбиття на куби дво- чи тривимірного простору. Один з найцікавіших прикладів клітинного автомата — гра "Життя".
Основний напрям дослідження клітинних автоматів — алгоритмічна вирішуваність якихось задач. Також розглядаються питання побудови початкових станів, при яких клітинний автомат вирішуватиме задану задачу. Залишається відкритим, наприклад, питання про можливість побудови машини Т'юрінга у грі "Життя".
[ред.] Див. також
 |
Це незавершена стаття з науки. Ви можете допомогти проекту, виправивши або дописавши її. |
