Последние новости
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, то заменяем его на a и ищем 1, которую заменяем на b, если при этом вышли за край последовательности, то, следовательно, 0 больше, поэтому стираем все остальные символы и пишем 0. Так же и с 1. Если же 1 и 0 не осталось, и при поиске попалась *, то 0=1, поэтому стираем все симолы и пишем =.