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

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

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

Основная программа

Все задачи ниже используют одну и ту же программу. Алфавит исполнителя — 0, 1 и пустой символ λ. Начальное состояние — q0. Головка стартует в ближайшей пустой ячейке справа от исходной последовательности.

Исходная последовательность состоит из N символов, среди которых только нули и единицы. Все ячейки слева и справа от последовательности заполнены символом λ.

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

Хвост нулей — это нули, которые стоят подряд в самом конце строки. Например, у строки 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 — нули после.

Когда K > 0

• Минимум: Z = K − 1 — берём самый короткий хвост t = 0, то есть строка заканчивается единицей.
• Максимум: Z = N − 1 — оставляем в исходной строке всего одну единицу, остальные символы делаем нулями.

Когда K = 0

Отдельный случай: исходная строка могла состоять только из нулей. После работы все нули превратятся в единицы, поэтому Z = N и для минимума, и для максимума.

Подробнее про максимум

Если K > 0, значение K влияет только на то, где именно стоит единственная единица в исходной строке, но не меняет максимальное количество нулей: их всё равно ровно N − 1. Подходящий шаблон исходной строки такой:

0 × (K − 1), затем 1, затем 0 × (N − K)

В такой строке ровно N − 1 нулей и одна единица. После работы хвостовые N − K нулей превратятся в единицы, а единица посередине — в ноль. На ленте останется K − 1 + 1 = K нулей, что и требовалось.

Математика решения

Обозначим:

• N — длина исходной последовательности;
• K — число нулей после выполнения программы;
• Z — число нулей в исходной последовательности;
• t — количество нулей в самом конце исходной последовательности.

Если строка не состоит целиком из нулей, её можно представить так:

u 1 0^t

где 0t — хвост из t нулей, 1 — ближайшая слева от этого хвоста единица, u — часть строки левее этой единицы.

Программа делает преобразование:

u 1 0^t → u 0 1^t

Поэтому число нулей после работы связано с исходным числом нулей формулой:

K = Z − t + 1, откуда Z = K + t − 1.

Для K > 0:

• минимальное возможное Z получается при t = 0 (строка заканчивается единицей): Z_min = K − 1;
• максимальное возможное Z получается, когда в исходной строке ровно одна единица, а остальные символы — нули: Z_max = N − 1.

Особый случай K = 0: исходная последовательность могла состоять только из нулей, тогда все нули превратились в единицы. И минимум, и максимум числа нулей в исходной последовательности равны N.

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

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

Готовые задачи

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

Ручной режим

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

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

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

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

Теоретическая часть

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