Машина Тьюринга — это абстрактная вычислительная модель, состоящая из:
- Ленты — бесконечной последовательности ячеек с символами
- Головки — устройства чтения/записи, указывающего на текущую ячейку
- Состояний — внутреннего состояния машины (q0, q1, q2, ...)
- Правил — инструкций перехода между состояниями
🔧 Формат записи правил:
состояние,символ,новый_символ,направление,новое_состояние
- состояние — текущее состояние (q0, q1, q2, ...)
- символ — символ под головкой (0, 1, □ или _ для пустой ячейки)
- новый_символ — символ для записи (0, 1, □ или _)
- направление — куда сдвинуть головку (L=влево, R=вправо, S=остаться)
- новое_состояние — следующее состояние или qhalt для остановки
💡 Подсказки по записи алгоритмов:
- Начинайте с состояния
q0
- Используйте
qhalt для остановки алгоритма
- Пустая ячейка:
□ или _ (для удобства записи)
- В визуальном отображении всегда показывается
□
- Направления:
L (влево), R (вправо), S (остаться)
- Каждое правило записывается на отдельной строке
- Если нет правила для текущего состояния и символа — машина остановится с ошибкой