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) растёт быстрее любой вычислимой функции - поэтому таблица выше останавливается на четырёх, а не на десяти
