“the configuration determines the possible behaviour of the machine.”
A. M. Turing, 1936, §1, p. 231. Здесь configuration — пара «m-configuration + scanned symbol»: состояние и прочитанный символ. Текст переведён в действия с физическими фишками; правила таблиц сохранены.
TURING MACHINE машина на фишках
ПУСТОТА ≠ НОЛЬТаблица поведения
| Состояние | Чтение | Действия | Далее |
|---|
Правило выбирается один раз, по символу в начале строки. Затем операции выполняются последовательно. Символ под головкой внутри строки может измениться; новая строка выбирается только после завершения прежней.
Щелчок по клетке меняет начальную ленту и начинает новый опыт. Пустая клетка обозначена контуром. Белая фишка 0 остаётся видимым объектом. Числовые адреса — наше средство наблюдения.
Формальная запись выбранного правила
Изменить машину
Как записывать правила
состояние | чтение | действия | следующее состояние
□ / None — только пустота. ANY — любой непустой символ. * — любой символ или пустота. 01 — ноль или единица. Совпадающие правила вызывают ошибку неоднозначности.
PUT:0 / PUT:1 — обеспечить нужную сторону фишки: разместить, если клетка пуста; перевернуть, если сторона противоположная. PUT:x — разместить фишку x. REMOVE — снять. FLIP — перевернуть уже имеющуюся двустороннюю фишку; на пустоте это ошибка. L/R — влево/вправо. Пустой список действий меняет только состояние.
Допустимы оригинальные сокращения P0, P1, Px, E. В исходной статье FLIP не является отдельной командой: это наша физическая реализация изменения 0 ↔ 1.