Подтема 4 из 6
Хвост и обратная задача
Какую часть строки меняет таблица задачи темы — и ответ: 11 нулей.
Хвост
Вернёмся к задаче темы: строка из 12 символов, после работы таблицы ровно 5 нулей. Сколько нулей могло быть до?
«На ленте исполнителя МТ в соседних ячейках записана последовательность из 12 символов, каждый из которых 0 или 1; остальные ячейки содержат пустой символ λ. В начальный момент головка находится в ближайшей справа от последовательности ячейке в состоянии q0. Программа работы исполнителя задана таблицей. После выполнения программы в последовательности оказалось ровно 5 нулей. Какое наибольшее количество нулей могло быть в исходной последовательности?»
| Состояние | λ | 0 | 1 |
|---|---|---|---|
q0 | λ, L, q1 | — | — |
q1 | λ, S, q1 | 1, L, q1 | 0, S, q1 |
Таблица меняет только хвост у правого края и одну цифру перед ним: P 1 0ᵗ → P 0 1ᵗ. Левая часть P не меняется. Здесь 0ᵗ — t нулей подряд, а не степень; 1ᵗ — t единиц. В подтеме 1 из 10100 получилось 10011: P = 10, хвост из двух нулей стал двумя единицами, единица перед ним — нулём.
Тактов t + 2: вход в строку, t нулей хвоста и остановочная замена единицы.
Откуда нули
Откуда в результате берутся 5 нулей?
Нули результата — это нули части P и один новый ноль из остановочной единицы. Поэтому в P было 5 − 1 = 4 нуля, а во входе — 4 + t нулей. Нули хвоста в результат не попадают: все они стали единицами. Значит, вопрос о входе сводится к вопросу о длине хвоста t.
Ответ задачи темы
Какое наибольшее t возможно при длине 12?
Хвост длиннее всего, когда во входе одна единица: 4 нуля левее неё, 7 правее. Тогда нулей во входе 4 + 7 = 11 — ответ задачи темы. Больше нельзя: из 12 нулей единица не появится, все станут единицами, и нулей в результате будет 0, а не 5. Наименьшее — при пустом хвосте t = 0: 4 нуля, например 111111100001 → 111111100000.
Граница — ещё не ответ: нужен вход, на котором она достигается. 000010000000 → 000001111111: в результате ровно 5 нулей, во входе 11.
При длине 12 можно перебрать все 2¹² = 4096 строк () и запустить каждую функцией run_tm из подтемы 1:
from itertools import productrules = { ('q0', 'λ'): ('λ', 'L', 'q1'), ('q1', 'λ'): ('λ', 'S', 'q1'), ('q1', '0'): ('1', 'L', 'q1'), ('q1', '1'): ('0', 'S', 'q1'),}least, best = 12, 0for bits in product('01', repeat=12): word = ''.join(bits) result, pos, steps = run_tm(word, rules, 12) if result.count('0') == 5: least = min(least, word.count('0')) best = max(best, word.count('0'))print(least, best)На экзамене строка из 999 символов: 2⁹⁹⁹ вариантов не перебрать. Рассуждение же не зависит от длины: наибольшее число исходных нулей — длина минус один.
Особые случаи
А если на ленте двоичная запись числа без ведущих нулей?
Любое дополнительное условие меняет границы — их считают заново, а не берут готовую формулу. Без ведущих нулей первая цифра — единица, и она входит в P. В P нужны эта единица и 4 нуля — 5 ячеек, ещё одна — остановочная единица, на хвост остаётся 12 − 6 = 6 нулей. Наибольшее число нулей — 4 + 6 = 10, например 100001000000.
Результат без нулей бывает только из строки, в которой одни нули: единица не встретится, и нового нуля не появится. Тогда нулей во входе ровно столько, какова длина.
Тонкости:зеркальная таблица
Если головка начинает слева и идёт вправо, меняя единицы на нули до первого нуля, хвост стоит у левого края: 1ᵗ 0 P → 0ᵗ 1 P. Рассуждают так же, только роли нулей и единиц меняются местами: единицы результата — единицы P и одна новая.
| Состояние | λ | 0 | 1 |
|---|---|---|---|
q0 | λ, R, q1 | — | — |
q1 | λ, S, q1 | 1, S, q1 | 0, R, q1 |
Итого
- ХвостP 1 0ᵗ → P 0 1ᵗ, P не меняется
- Тактыt + 2
- Нули результатанули P и один новый
- Наибольшееодна единица, длина − 1 нулей
- Наименьшеепустой хвост, t = 0
- Проверкапример входа и перебор на короткой длине
Проверьте себя
Ответь сначала сам, потом открой ответ.
1000000?ОтветСкрыть ответ
ОтветСкрыть ответ
1000000000 → 0111111111.ОтветСкрыть ответ
1111111111 → 1111111110.ОтветСкрыть ответ
ОтветСкрыть ответ
Практика
Для проверки ответов нужен JavaScript. Условия, подсказки и решения доступны ниже.
Такты на слове 1000000
На ленте исполнителя МТ записано слово 1000000, остальные ячейки пустые (λ). Головка — в ближайшей пустой ячейке справа от строки, состояние q0. Программа:
| Состояние | λ | 0 | 1 |
|---|---|---|---|
| q0 | λ, L, q1 | — | — |
| q1 | λ, S, q1 | 1, L, q1 | 0, S, q1 |
Сколько тактов выполнит исполнитель, включая такт с остановкой?
Введите число.
Подсказка
Хвост из шести нулей.
Решение
Хвост из t нулей даёт t + 2 такта: вход, шесть нулей и остановочная замена единицы — 8.
Ответ: 8
Один ноль в результате
На ленте исполнителя МТ записана последовательность из 10 символов, каждый из которых 0 или 1 (начальные нули допускаются), остальные ячейки пустые (λ). Головка — в ближайшей пустой ячейке справа от строки, состояние q0. Программа:
| Состояние | λ | 0 | 1 |
|---|---|---|---|
| q0 | λ, L, q1 | — | — |
| q1 | λ, S, q1 | 1, L, q1 | 0, S, q1 |
После выполнения в последовательности ровно один ноль. Какое наибольшее количество нулей могло быть в исходной последовательности?
Введите число.
Подсказка
Хвост из нулей должен быть самым длинным.
Решение
Единственный ноль результата — новый, из единицы, левее неё нулей нет. Хвост длиннее всего, когда единица первая: 1000000000 → 0111111111, нулей 9.
Ответ: 9
Наименьшее число нулей
На ленте исполнителя МТ записана последовательность из 15 символов, каждый из которых 0 или 1 (начальные нули допускаются), остальные ячейки пустые (λ). Головка — в ближайшей пустой ячейке справа от строки, состояние q0. Программа:
| Состояние | λ | 0 | 1 |
|---|---|---|---|
| q0 | λ, L, q1 | — | — |
| q1 | λ, S, q1 | 1, L, q1 | 0, S, q1 |
После выполнения в последовательности ровно шесть нулей. Какое наименьшее количество нулей могло быть в исходной последовательности?
Введите число.
Подсказка
Нули результата — нули левой части и один новый.
Решение
Машина меняет нули справа на единицы и ближайшую единицу на ноль. Шесть нулей результата — пять нулей левой части и один новый. Нулей во входе меньше всего, когда хвост пустой: 5, например 111111111000001.
Ответ: 5
Результат без нулей
На ленте исполнителя МТ записана последовательность из 7 символов, каждый из которых 0 или 1 (начальные нули допускаются), остальные ячейки пустые (λ). Головка — в ближайшей пустой ячейке справа от строки, состояние q0. Программа:
| Состояние | λ | 0 | 1 |
|---|---|---|---|
| q0 | λ, L, q1 | — | — |
| q1 | λ, S, q1 | 1, L, q1 | 0, S, q1 |
После выполнения нулей в последовательности нет. Сколько нулей было в исходной последовательности?
Введите число.
Подсказка
Без нулей результат бывает только у одного входа.
Решение
Если во входе есть единица, она станет нулём. Значит, единиц не было: все семь символов — нули, они стали единицами.
Ответ: 7
Без ведущих нулей
На ленте исполнителя МТ в соседних ячейках записано двоичное представление натурального числа без ведущих нулей, остальные ячейки пустые (λ). Головка — в ближайшей пустой ячейке справа от строки, состояние q0. Программа:
| Состояние | λ | 0 | 1 |
|---|---|---|---|
| q0 | λ, L, q1 | — | — |
| q1 | λ, S, q1 | 1, L, q1 | 0, S, q1 |
Запись числа состоит из 12 цифр, после выполнения в ней ровно пять нулей. Какое наибольшее количество нулей могло быть в исходной записи?
Введите число.
Подсказка
Первая цифра — единица, она в неизменной части.
Решение
Пять нулей результата — четыре нуля неизменной части и один новый. Неизменная часть начинается с единицы и содержит четыре нуля — пять цифр, ещё одна — остановочная единица, на хвост остаётся шесть нулей. Нулей 4 + 6 = 10, например 100001000000.
Ответ: 10
Зеркальная таблица: наибольшее
На ленте исполнителя МТ записана последовательность из 10 символов, каждый из которых 0 или 1 (начальные нули допускаются), остальные ячейки пустые (λ). Головка — в ближайшей пустой ячейке слева от строки, состояние q0. Программа:
| Состояние | λ | 0 | 1 |
|---|---|---|---|
| q0 | λ, R, q1 | — | — |
| q1 | λ, S, q1 | 1, S, q1 | 0, R, q1 |
После выполнения в последовательности ровно четыре единицы. Какое наибольшее количество единиц могло быть в исходной последовательности?
Введите число.
Подсказка
Машина идёт слева направо и меняет единицы на нули до первого нуля.
Решение
Единицы слева до первого нуля становятся нулями, первый ноль — единицей. Четыре единицы результата — новая и три из правой части. Больше всего единиц, когда ноль один: например, 1111110111 → 0000001111, единиц 9.
Ответ: 9
Зеркальная таблица: наименьшее
На ленте исполнителя МТ записана последовательность из 10 символов, каждый из которых 0 или 1 (начальные нули допускаются), остальные ячейки пустые (λ). Головка — в ближайшей пустой ячейке слева от строки, состояние q0. Программа:
| Состояние | λ | 0 | 1 |
|---|---|---|---|
| q0 | λ, R, q1 | — | — |
| q1 | λ, S, q1 | 1, S, q1 | 0, R, q1 |
После выполнения в последовательности ровно четыре единицы. Какое наименьшее количество единиц могло быть в исходной последовательности?
Введите число.
Подсказка
Хвост из единиц может быть пустым.
Решение
Четыре единицы результата — новая и три из правой части. Меньше всего единиц, когда слева единиц нет: 0111000000 → 1111000000, единиц 3.
Ответ: 3