tarosha_yakubovich

Ниже приводится один из вариантов описания машины Тьюринга, которая по входу вида   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. Фаза «сканирование и запоминание» ────────