Построй машину Тьюринга (МТ), переводящую 1^k 0^m 1^n -> 1^A 0^B 1^C

Где A = m; B = 2; C = k

Ниже приводится один из вариантов описания машины Тьюринга, которая по входу вида

  1^k 0^m 1^n

выдаёт на ленте слово

  1^A 0^B 1^C  где A = m, B = 2, C = k.

Заметим, что вход состоит из трёх блоков: сначала k единиц, затем m нолей и, наконец, n единиц, а выход должен состоять из «считанного» числа m (выводится в виде m единиц), затем ровно двух нолей и затем k единиц (то есть столько, сколько было в начале входа).

Важно понимать, что при построении Тьюринговой машины (МТ) можно использовать различные приёмы («метод копирования», «метод стирания» и т.п.). Один из вариантов решения состоит из двух основных фаз:

──────────────────────────────
1. Фаза «сканирование и запоминание»
──────────────────────────────
Мы хотим «выделить» две величины:
 • m – число нолей (средний блок входа),
 • k – число единиц в первом блоке входа.
При этом остаток входа (n единиц после нолей) не важен.

Чтобы сохранить информацию (учесть количество символов) на однолентной МТ, можно «перекодировать» её следующим образом. Заводим два разных типа меток:
 – пусть изначальные единицы из первого блока будут при просмотре заменяться на символ X (то есть X запоминает, что там была единица, которую надо в будущем перепечатать);
 – нули из среднего блока будем помечать символом Y при их «учёте».
При этом во время прохода по ленте МТ «скопируем» (с помощью перемещения по ленте) числа m и k в специальные области ленты.

Один из вариантов алгоритма:

A) Переход к первому появлению 0. На первом проходе из состояния q₀ будем идти справа, и все встреченные 1 (из первого блока входа) заменять на X (это–метка того, что “учтена единица” и её потом надо будет вывести в правой части результата). Когда первый раз встретится 0, переход – сигнал начала обработки блока нолей.

B) Обработка блока нолей: из состояния q₁ находим подряд м нолей. При каждом прохождении по нулю мы:
 – заменяем найденный 0 на Y;
 – перемещаемся влево до специальной области (например, до левой части ленты, где «накапливаем» копию числа m в виде единиц). Там добавляем одну единицу (например, записывая символ 1) и возвращаемся к месту обработки.

Таким образом, после обработки всех нолей, в особой области ленты появится m единиц. (Можно, например, выделить левый участок ленты для хранения «счётчика нолей».)

C) После того как блок нолей закончен (при встрече с 1, или если нолей больше нет), машина продолжает проход справа, игнорируя n единиц в конце входа.

──────────────────────────────
2. Фаза «перезапись»
──────────────────────────────
Теперь на ленте имеют место быть две накопленные части:
 (1) в левом участке – m единиц, которые мы получили из среднего (перекодированного) блока;
 (2) в первой части ленты в виде X – метки, соответствующие исходным единицам первого блока (их ровно k).
Далее МТ выполняет стирание исходного содержимого и в новом режиме записывает результат по требованию:
 • Сначала записываются m единиц (то есть копия накопленного счётчика нолей);
 • Затем записываются ровно два нуля (B = 2);
 • Затем, в конец, перепечатывается последовательность, состоящая из k единиц (при этом каждую метку X заменяем на 1).

Таким образом, итоговый результат будет иметь вид:
  (м единиц) 0 0 (k единиц),
то есть 1^m 0^2 1^k, что совпадает с требуемым, поскольку по условию A = m, B = 2, C = k.

──────────────────────────────
Формальное описание (на уровне таблицы переходов)
──────────────────────────────
Обозначим:
 – Σ = {0,1} – входной алфавит;
 – Γ = {0, 1, X, Y, ␣} – рабочий (ленточный) алфавит (␣ – пустой символ).
Начальное состояние: q₀; конечное – q_f.

Ниже приведён один из вариантов таблицы переходов (здесь запись имеет вид: δ(состояние, символ)= (новый символ, направление, новое состояние)). Некоторые вспомогательные состояния используются для перемещения и копирования.

1. Обработка первого блока:
 (q₀, 1) = (X, R, q₀)
  – Пока читаем 1, заменяем на X (запоминаем, что встретили единицу) и двигаемся вправо.
 (q₀, 0) = (0, R, q₁)
  – При первом появлении 0 переходим в состояние q₁ для обработки блока нолей.
 (q₀, Y) = (Y, R, q₀)  (на случай если встретились уже помеченные символы)
 (q₀, ␣) = (␣, R, q₂)  (если сразу закончился вход – нет блока нолей; здесь можно задать особую процедуру)

2. Обработка блока нолей (состояние q₁):
 (q₁, 0) = (Y, L, q₃)
  – При встрече 0 заменяем его на Y, переходим влево (состояние q₃ – для копирования «1» в область счётчика нолей).
 (q₁, 1) = (1, R, q₄)
  – Если после нолей встретилась 1, переходим в q₄ – завершаем копирование нолей.
 (q₁, Y) = (Y, R, q₁)
  – Если уже Y, просто продолжаем.
 (q₁, ␣) = (␣, R, q₄)
  – Конец блока нолей можно определить по пустому символу.

3. Копирование для каждого 0 (состояние q₃):
 Цель – перейти в левый участок ленты, где накоплен счётчик нолей.
 (q₃, 0) = (0, L, q₃), (q₃, 1) = (1, L, q₃), (q₃, X) = (X, L, q₃), (q₃, Y) = (Y, L, q₃)
  – Двигаемся влево до специального разделителя (например, до крайнего левого символа, либо до ␣).
 (q₃, ␣) = (1, R, q₅)
  – Когда дошли до пустого места слева, запишем 1 (это и есть один «единичный» элемент счётчика, соответствующий одному нулю во входе), и переходим вправо в состояние q₅ для возвращения в место, где остановились.

4. Возвращение в правую часть (состояние q₅):
 (q₅, 1) = (1, R, q₅), (q₅, X) = (X, R, q₅), (q₅, Y) = (Y, R, q₅), (q₅, 0) = (0, R, q₅)
 (q₅, ␣) = (␣, L, q₁)
  – Дойдя до конца (или до места, где ранее останавливали обработку нолей), возвращаемся в q₁ для продолжения обработки следующего 0.

5. После обработки нолей переходим в стадию «перезаписи»
 Состояние q₄ – когда блок нолей закончен (встретился символ 1 или ␣). Здесь МТ идёт вправо, пропуская оставшиеся 1 (блок n не важен). Затем, достигнув ␣ (конца исходного слова), переходим к фазе очистки и записи нового результата.
 (q₄, 1) = (1, R, q₄)
 (q₄, ␣) = (␣, L, q₆)

6. Очистка исходной записи (состояние q₆):
 Машина возвращается к началу ленты и стирает старые символы, оставляя только накопленную информацию (на левом участке – m единиц, а в районе, помеченном X – метки для k).
 Процедуру можно описать так: двигаясь вправо, заменить все встреченные (0, X, Y, 1) на ␣, при этом запомнив (с помощью переходов) где и что надо переписать.
 После очистки переходим в состояние q₇ для записи результата.

7. Запись результата (состояние q₇):
 Мы записываем на пустой ленте сначала m единиц. Эти единицы уже были скопированы в левый участок ранее (при переходе в q₃ – там мы дописывали единицу каждый раз, когда встречали 0).
 Затем производим запись двух нолей – задав переход
  (q₇, ␣) = (0, R, q₈)
  (q₈, ␣) = (0, R, q₉)
 После чего переходим в состояние q₁₀, в котором сканируем область, где остались метки X, и заменяем каждую X на 1 (выводим k единиц).
 Например:
  (q₉, X) = (1, R, q₉)
  (q₉, ␣) = (␣, R, q_f)

Конечное состояние q_f означает завершение работы МТ.

──────────────────────────────
Замечания
──────────────────────────────
1. Описанный выше вариант – один из многих. При его реализации можно выбрать иные способы «сохранить» число символов: можно использовать специальные разделители (например, символ “#”) для разбиения ленты на области, либо использовать маркировку справа от исходного слова.
2. Главное – добиться того, чтобы итоговая запись на ленте состояла из:
 – m единиц (это значение A), затем
 – точно двух нолей (B = 2), затем
 – k единиц (это и есть C).
3. Если исходная МТ устроена так, что входная конфигурация имеет вид … ␣ 1 1 … 1 0 0 … 0 1 1 … 1 ␣ … , то можно “переписать” содержимое в новом формате на том же поле или даже поверх исходного слова, если обеспечить достаточное пространство и использовать вспомогательные метки.

──────────────────────────────
Вывод
──────────────────────────────
Таким образом, одна из машин Тьюринга, решающих задачу, может быть описана следующей схемой:
 • На первом проходе МТ сканирует первый блок 1 и заменяет их на X (запоминая k);
 • Затем при переходе в состояние q₁ обрабатывает блок нолей, где для каждого 0 (заменяемого на Y) в специальную область дописывается единица (накапливая число m);
 • После обхода оставшейся части входа МТ переходит в режим очистки и записи, где стирает исходное слово и на чистой ленте записывает сначала m единиц, затем “00” и, наконец, k единиц (полученных заменой X на 1).
В итоге получаем требуемое преобразование: 1^k 0^m 1^n → 1^m 0^2 1^k.

Это и есть построение искомой Тьюринговой машины.

──────────────────────────────
Заключение
──────────────────────────────
При сдаче задания можно представить такое высокоуровневое описание алгоритма работы МТ вместе с таблицей переходов (как приведено выше) и пояснением, как именно с помощью вспомогательных символов (X, Y) и областей ленты происходит запоминание необходимых подсчётов. Такой вариант решения удовлетворяет условию задачи.