Правило 110

Правило 110 — елементарний одновимірний клітинний автомат з поведінкою, яка перебуває на кордоні хаосу і стабільності. В цьому відношенні Правило 110 ідентично грі «Життя». Відомо, що Правило 110 є Тьюринг-повним, що означає, що будь-яка обчислювальна процедура може бути реалізована за допомогою цього клітинного автомата.

Історія

Меттью Кук представив свій доказ на конференції Інституту Санта-Фе у 1998 році, але Стівен Вольфрам заборонив включати цей доказ в паперову версію матеріалів конференції, бо не хотів, щоб воно було опубліковано до видання книги A New Kind of Science. 2004 року доказ Кука було опубліковано в журналі Вольфрама «Комплексні системи» (випуск 15, том 1), через 10 років після того, як Кук вперше представив його.

Визначення

В найпростіших клітинних автоматах одновимірний масив нулів і одиниць оновлюється відповідно до набору простих правил. Значення клітини на наступному кроці залежить від значень клітин-сусідів на поточному кроці та значення самої клітини. Для Правила 110 діє наступний набір правил:

Поточний стан	111	110	101	100	011	010	001	000
Новий стан центральної клітини	0	1	1	0	1	1	1	0

Найменування Правило 110 названо правилом тому, що бінарна послідовність 01101110 при перекладі в десяткову систему дасть число 110.

«Життя» Конвея та інші клітинні автомати

Класи конфігурацій

Осцилятор • Натюрморт • Космічний корабель • Рушниця^[en] • Паровоз^[en] • Пожирачі • Відбивач • Розмножувач^[en] • Довгожитель^[en] • Заповнювач^[en]

Конфігурації

Планер • Блок • Едемський сад • R-пентаміно • Пентадекатлон

Терміни

Окіл Мура • Окіл фон Неймана • Швидкість світла

Інші КА на
двомірній решітці

Автомат фон Неймана • Клітинний автомат Нобілі • Wireworld • Мурашка Ленгтона • HighLife^[en] • Day & Night^[en]

Одномірні КА

Правило 30 • Правило 110 • Правило 184 • Задача синхронізації стрільців

ПЗ і алгоритми

Golly^[en] • Hashlife^[en]

Дослідники КА

Джон Конвей • Білл Госпер^[en] • Мартін Гарднер • Річард Ґай • Брайан Сільверман^[en] • Джон Уайлдер Т'юкі • Джон фон Нейман • Едвард Форрест Мур • Стівен Вольфрам

Ця стаття є заготовкою. Ви можете допомогти проєкту, доробивши її. Це повідомлення варто замінити точнішим.

Ця стаття не містить посилань на джерела. Ви можете допомогти поліпшити цю статтю, додавши посилання на надійні (авторитетні) джерела. Матеріал без джерел може бути піддано сумніву та вилучено. (листопад 2014)