Последние новости
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.
Вначале убираем по очереди нули и единицы (по одному), помечая их, чтобы не выглядели, как пустая клетка ленты. Когда остаются только нули или только единицы, убираем всё, а в конце пишем соответствующую цифру. Если цифр не остаётся, всё стираем и пишем "=".