Машина Тьюринга: Например, команда 0, L, q3 выполняется; 343, 0, 1000, 1 · ЕГЭ №12

Команда λ, L, q1 переводит головку влево, на младший разряд последовательности.

В состоянии q1 ноль заменяется единицей со сдвигом влево (1, L, q1), единица заменяется нулём с остановкой (0, S, q1), а на пустой ячейке машина просто останавливается. Это вычитание единицы.

Пусть справа стоит хвост из t нулей, а перед ним единица. Эти t нулей станут единицами, а единица станет нулём, поэтому число нулей меняется на –t + 1.

Если нулей было Z, то стало Z – t + 1 = 343, отсюда Z = 342 + t: чем длиннее нулевой хвост, тем больше нулей было изначально.

Хотя бы одна единица в последовательности быть обязана, иначе машина сразу дошла бы до пустой ячейки, поэтому Z ≤ 999 и t ≤ 657.

Берём t = 657: 342 нуля, затем единица, затем 657 нулей — всего 1000 символов, из них 999 нулей. После работы программы нулей остаётся 342 + 1 = 343, что и требуется.

Максимально возможное число нулей в исходной последовательности — 999.

$\textbf{Ответ: 999.}$