Правило 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.
 | Ця стаття не містить посилань на джерела. (листопад 2014) |