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