Машина Тьюринга онлайн

Как работает эмулятор машины Тьюринга

Машина Тьюринга — исполнитель с бесконечной лентой, головкой и таблицей переходов. На каждом шаге головка читает символ в клетке, записывает новый, сдвигается и переходит в другое состояние. Эмулятор Neuronis работает в браузере бесплатно: задайте ленту, заполните таблицу и запустите программу целиком или по шагам.

Как записать команду

Строки таблицы — состояния (q0, q1…), столбцы — символы на ленте, первый столбец — пустая клетка λ. В ячейке пишется команда через запятую: символ, направление, состояние, например 0, R, q1.

• L — сдвиг влево, R — вправо;
• N — головка остаётся на месте;
• S — остановка машины;
• λ (или lambda) — записать пустую клетку.

Машина Тьюринга в задании 12 ЕГЭ

В ЕГЭ по информатике машина Тьюринга встречается в задании 12: нужно понять, что делает программа с числом или строкой на ленте, и найти ответ. Режим «Десятичное число» переводит число в двоичную запись на ленте, а после остановки эмулятор показывает результат в десятичном виде — удобно для проверки ответа.