1.6 KiB
1.6 KiB
Бэклог
Машина Тьюринга на ДЛМ («усердный бобёр»)
Идея для следующей статьи на Хабре, если первая хорошо зайдёт.
ДЛМ — комбинационная схема без памяти, но таблицу правил машины Тьюринга она посчитать может. Лента на бумаге и память о состоянии — на человеке. Получается «ДЛМ + человек = машина Тьюринга».
«Усердный бобёр» с двумя состояниями (A0 → 1RB, A1 → 1LB, B0 → 1LA, B1 → 1RH) помещается в машину:
- входы: А — состояние (0 = A, 1 = B), Б — прочитанный символ, В не нужен;
- выходы: V — что записать (всегда 1), X — сдвиг вправо, Y — следующее состояние B, Z — стоп;
- столбцы: 1 — всё «оба гнезда» → V; 2 — ¬А·¬Б → X; 3 — А·Б → X; 4 — ¬А → Y; 5 — А·Б → Z;
- 5 столбцов из 7, 22 штеккера из 30, 5 перемычек из 7.
Бобёр на три состояния в лоб не помещается: при прямом кодировании нужно 9 столбцов. Другие кодировки не перебирались.
Для эмулятора: программа «Машина Тьюринга» и полоска ленты рядом с пультом, по которой человек водит головку по ответам ламп.