«Критери» () — блоковий клітинний автомат, що виявляє поведінку, схожу з грою «Життя» Конвея; зокрема, повний за Тюрінгом. .. Вперше описали 1987 року, як і деякі інші оборотні клітинні автомати, та ..

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

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

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

Поведінка

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

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

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

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

Примітки