Последние новости
03.04.24
Предварительные результаты финального тура
05.03.24
Проведение финального тура
01.01.24
Предварительные результаты
25.12.23
Отборочный этап завершён.
18.12.23
Отборочный этап продлён по 24 декабря включительно
Постройте машину Тьюринга, на ленте которой в начале работы находится набор из нулей и единиц. После окончания работы на ленте должна быть «1», если число единиц больше числа нулей, «0» — если меньше и «=» в случае равенства. Кроме «0», «1» и «=»
можно использовать вспомогательные символы «a» и «b».
В качестве начального решения приведена последовательность команд, которая 1) удаляет текущий символ, 2) все символы, находящиеся правее него, сдвигает на одну позицию влево, 3) возвращает считывающую головку в начальную позицию. Последовательность запускается переходом в состояние t1. В ней использованы состояния q0, q1, qa, qb, q=, q3, q4, q5. Последовательность команд заканчивает работу в состоянии t2.
При добавлении новых команд не забывайте, что для машины Тьюринга их порядок не существенен.
Начальное состояние s, конечное f.
Алгоритм работы машины: При нахождении 0 меняем его на а и двигаемся по ленте вправо. Если дошли до * (конец ленты) -- то переходим в qa(состояние для стирания ленты и вывод 0) (нулей больше) Иначе при нахождении 1 меняем ее на b и двигаемся по ленте влево до начала(q3), затем просматриваем последовательно все ячейки ленты с начала. При нахождении 1 меняем ее на а и двигаемся по ленте вправо. Если дошли до * (конец ленты) -- то переходим в qb(состояние для стирания ленты и вывод 1) (единиц больше) Иначе при нахождении 0 меняем его на a и двигаемся по ленте влево до начала(q3), затем просматриваем последовательно все ячейки ленты с начала. Если просмотрены все ячейки ленты (дошли до *), то двигаемся влево (q4). При нахождении непарного числа меняем состояние на qa или qb(стирание ленты и вывод 0 или стирание ленты и вывод 1). При проходе ленты до конца меняем состояние на (стирание ленты и вывод =).