Граблі (конфігурація клітинного автомата)

Граблі́ — різновид паротяга — конфігурації, яка залишає слід зі сміття. Граблі залишають сміття у вигляді потоку космічних кораблів^[1].

Зв'язка з грабель у грі "Життя"

У грі «Життя» відкриття граблів було одним із ключових компонентів, необхідних для формування розмножувачів, першої відомої моделі в житті, в якій кількість живих клітин зростає квадратично. Розмножувач формується з'єднанням кількох граблів так, щоб планери — найменші можливі космічні кораблі — генерували, взаємодіючи (це називається планерним синтезом), послідовність планерних гармат, які продукують планери. Отримані планери заповнюють на ігровому полі трикутник, що збільшується з часом.^[2] У загальнішому сенсі, якщо для правила клітинного автомата (математична функція, що визначає картину наступного покоління, яка отримувану з даної конфігурації живих і мертвих клітин) існують граблі, часто можна побудувати паротяги, які залишають слід із об'єктів багатьох інших типів, забезпечивши зіткнення потоків космічних кораблів. Як пише Девід Белл:

Вони дуже важливі для гри «Життя», оскільки їх вихлоп можна використовувати для створення інших об'єктів; ці конфігурації можуть проводити сигнали для емуляції логічних операцій. Коли б не було знайдено новий паровоз, важливим завданням є «приручити» його, так що його «брудні» вихлопи стали «чистими» вихлопами, які складаються, наприклад, із планерів.

Оригінальний текст (англ.)

They are extremely important in Life because the output can be used to construct other objects and can pass signals around to perform logic operations. Whenever any new puffer engine is found an important goal is to "tame" it so that its useless "dirty" exhaust is converted into "clean" exhaust, particularly gliders.

Першими граблями були виявлені на початку 1970-х років «космічні граблі», які рухаються зі швидкістю с/2 (або долають одну клітинку за два покоління), випускаючи планер кожні двадцять поколінь.^[3] Нині для «Життя» відомі граблі, які рухаються ортогонально зі швидкостями с/2, с/3, с/4, с/5, 2с/5, 2с/7, с/10^[4] і 17с/45, і по діагоналі зі швидкостями с/4 і с/12, із багатьма різними періодами.^[5] Граблі також відомі в деяких інших клітинних автоматах, що є різновидами «Життя», наприклад, «Highlife»,^[6] «День і ніч»,^[7] і «Насіння».^[8]

Готтс (1980) показує, що космічні граблі в «Житті» можуть утворитися внаслідок «стандартної послідовності зіткнень», в якій один планер взаємодіє з широко розділеним набором 3-клітинних початкових блоків (блимавки і блоки). Як наслідок, він знаходить нижні межі ймовірності того, що ці конфігурації утворюються в будь-якій досить розрідженій і досить великій випадковій початковій позиції гри «Життя». Цей результат приводить до стандартних послідовностей зіткнень для багатьох інших моделей, таких як розмножувачі.^[9]