Правило 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.