Задачи на машину Тьюринга

Программа машины одна для всех задач

Исполнитель — головка, движущаяся по бесконечной ленте. В каждой ячейке — символ 0, 1 или пустой символ λ. Команда имеет вид новый_символ, движение, новое_состояние.

Начальное состояние — q0. Головка стартует в ближайшей пустой ячейке справа от исходной строки.

Разобраться с нуля 5 шагов

Этот блок лучше пройти перед генератором. Он объясняет идею не через готовую формулу, а через короткие строки.

Мини-тренажёр: хвост нулей ключ к задаче

Хвост нулей — это нули, которые стоят подряд в самом конце строки. Например, у строки 101000 хвост 000, значит t = 3. Если строка заканчивается единицей, то t = 0.

Как думать в таких задачах

1. Сначала смотрим на правый конец строки.
2. Обозначаем через t количество нулей на самом конце.
3. Если в строке есть единица, машина превращает u 1 0t в u 0 1t.
4. Поэтому из числа нулей исчезают t хвостовых нулей, но появляется один новый ноль.
5. Получаем формулу K = Z − t + 1, где Z — нули до работы, K — нули после.
6. Для минимума берём самый маленький хвост: t = 0, поэтому Z = K − 1.
7. Для максимума оставляем в исходной строке всего одну единицу, поэтому Z = N − 1.
8. Случай K = 0 разбирается отдельно: исходная строка могла быть вся из нулей, значит Z = N.

Теория

• Лента — бесконечная последовательность ячеек, по одному символу в каждой.
• Головка — устройство, которое читает символ текущей ячейки и записывает новый.
• Состояние — внутренний режим головки. В этой программе есть q0 и q1.
• λ — пустой символ.
• L — влево, R — вправо, N — стоять, S — остановиться после команды.
• Строки таблицы — состояния, столбцы — символы под головкой. На пересечении написано действие.

Генератор задач

Случайные N от 50 до 2000 и корректное K от 0 до N. Чаще выбирается K > 0, чтобы задача не сводилась к особому случаю.

Готовые примеры

Три задачи из исходных материалов. Их можно загрузить в текущую задачу.

Ручной режим

Задайте свои N и K и выберите, что искать. Дробные значения не принимаются.

Текущая задача

Симулятор машины Тьюринга

Введите короткую двоичную строку. Кнопка «Один шаг» теперь сразу выполняет первый переход, даже если симуляция ещё не была запущена.