Критери

«Критери» (англ. Critters) — блоковий клітинний автомат, що виявляє поведінку, схожу з грою «Життя» Конвея; зокрема, повний за Тюрінгом^[1][2]. Вперше описали 1987 року, як і деякі інші оборотні клітинні автомати, Томмазо Тоффолі та Норман Марґолус^[3].

«Критери» визначені на квадратній ґратці, двовимірній і нескінченній. Як і в «Житті», в будь-який момент часу кожна комірка перебуває в одному з двох станів: жива або мертва. При цьому «Критери» — блоковий клітинний автомат, що використовує окіл Марґолуса. Це означає, що на кожному кроці ґратку поділено на блоки 2×2, кожен з яких оновлюється окремо від інших. При цьому після кожного кроку поділ на блоки змінюється: вони зсуваються на одну комірку по горизонталі та вертикалі; таким чином, всі чотири комірки будь-якого блоку на наступному кроці опиняються в різних блоках.^[3]

Функція переходу «Критерів» залежить від кількості живих комірок у блоці: якщо їх дві, блок не змінюється; якщо їх нуль, один або чотири, то стан кожної комірки блоку змінюється на протилежний. У разі трьох живих комірок перетворення відбувається у два етапи: стан кожної комірки змінюється на протилежний, а весь блок повертається на 180°. Оскільки кількість живих комірок у будь-якому разі змінюється на кількість мертвих, а операції для кожного з чисел комірок окремо оборотні, ці правила задають оборотний клітинний автомат.^[3] .

Альтернативна версія функції переходу змінює стани на протилежні лише у блоках із двома живими комірками, а також обертає на непарних кроках усі блоки з трьома живими комірками, а на парних — з однією. Така версія відрізняється від стандартної тим, що вона не змінює кількості живих комірок, і при цьому має схожу динамічну поведінку^[2].

Як і для будь-якого оборотного клітинного автомата, якщо початковий стан «Критерів» вибрати випадково, то в процесі еволюції стан залишиться невпорядкованим^[1][3]. Але якщо почати з невеликої кількості випадкових комірок усередині великої ділянки мертвих комірок, то з центральної ділянки пошириться багато маленьких шаблонів, подібних до планера з гри «Життя», які будуть складно взаємодіяти^[1][2][3]. Загалом, «Критери» допускають складні космічні кораблі та осцилятори з нескінченним числом різних періодів^[2].

Існує гіпотеза, що за вибору періодичних граничних умов (тобто при склеюванні країв прямокутного поля, в наслідок чого виходить тор) початкові положення з кількістю живих комірок достатньо малою, порівняно з розміром поля, мають високу ймовірність виникнення стану, в якому полем випадково блукає один планер^[4].

У грі «Життя» зіткнення космічних кораблів можуть призвести до взаємознищення, стабільної конфігурації або осцилятора, що неможливо для оборотного клітинного автомата. Натомість будь-яке зіткнення має призвести до появи хоча б одного космічного корабля^[1][4], а при симетричному зіткненні двох космічних кораблів з'являється симетричний набір з двох або більше космічних кораблів^[1]. Якщо розрахувати початковий стан так, щоб місця зіткнень були правильними, у «Критерах» можна симулювати більярдний комп'ютер на планерах і, подібно до гри «Життя», довести повноту за Тюрінгом^[1].

Попри складність поведінки, у «Критерах» діють деякі закони збереження та є різні симетрії. Наприклад, парність числа живих комірок уздовж деяких діагоналей не змінюється. Крім того, якщо початкова конфігурація має скінченне число живих комірок, то після парного числа кроків число живих комірок є таким самим (а після непарного числа кроків таким стає число мертвих комірок)^[1]. На відміну від багатьох оборотних клітинних автоматів, досліджених Тоффолі та Марґолусом, «Критери» не переходять у себе при оберненні напряму часу; однак вони переходять самі в себе при одночасному оберненні напрямку часу та заміні кожного стану на протилежний^[3].