Math
Машина Тюрінга та «заклопотані бобри»
Паперова стрічка між двома котушками, металева головка з лампою стану і таблиця правил. Кожен крок програється як читання, запис, зсув, новий стан; журнал унизу зберігає весь прогін, а правка правила лишає старий прогін привидом. Рекорди знайдено перебором усіх машин, а не процитовано.
Що відбувається
У такої машини є таблиця і більше нічого: для кожного стану і символу — що записати, куди зсунутися, в який стан перейти — або зупинитися. На столі це прилад: паперова стрічка між двома котушками, головка на рейках і лампа, що показує її стан. Кожен крок програється у чотири фази — головка читає клітинку, штампує нову цифру, зсувається на клітинку, лампа змінює колір, — а аркуш унизу веде журнал: кожен крок прогону як теплова карта з віссю часу. Клацни по кроку — машина завмре на ньому. Клацни по жетону таблиці — правило зміниться, а прогін до правки лишиться скляним привидом поруч із новим, з позначкою кроку, де дві історії розходяться. Заклопотаний бобер питає, як довго така машина може працювати до зупинки. Рекорди тут не процитовано: всі 64 одностанові машини, всі 20736 двостанових і 1048576 тристанових у нормальній формі побудовано й прогнано — три стани дають щонайбільше 21 крок і щонайбільше 6 одиниць, двома різними машинами. Чотири стани коштували б 268 мільйонів машин, тому їхнього чемпіона взято відомим і перевірено прогоном: 107 кроків, 13 одиниць. Машина, що дійшла до стелі у 400 кроків, не зупинилася, і ніщо на цій картці не скаже, чи зупиниться вона колись.
Рівняння модуля
Рівняння машина є таблицею: для кожної пари (стан, символ) вона вказує, що записати, куди рухатися (L або R) і який стан буде наступним - або H, зупинка стрічка спочатку заповнена нулями й необмежена; вікно картки вміщує 49 клітинок, чого вистачає для кожної машини, яку вона запускає S(n) - найбільша кількість кроків, яку робить будь-яка машина з n станами, що зупиняється; Σ(n) - найбільша кількість одиниць, яку залишає будь-яка з них знайдено тут перебором, а не процитовано: n = 1 дає 64 машини, n = 2 дає 20736, n = 3 дає 16^5 = 1048576 у нормальній формі (перший хід 1RB) S(1) = 1, Σ(1) = 1; S(2) = 6, Σ(2) = 4; S(3) = 21, Σ(3) = 6 - і для n = 3 це дві РІЗНІ машини підвищення ліміту кроків з 25 до 200 не додає жодної машини, що зупиняється: кожна 3-станова машина, яка зупиняється, зупиняється до кроку 21 n = 4 коштувало б 16^7 = 268435456 машин, тому її чемпіон береться як відомий і перевіряється запуском: 107 кроків, 13 одиниць S(n) зростає швидше за будь-яку обчислювану функцію - саме тому таблиця вище зупиняється на чотирьох, а не на десяти
