Последние новости
03.04.24
Предварительные результаты финального тура
05.03.24
Проведение финального тура
01.01.24
Предварительные результаты
25.12.23
Отборочный этап завершён.
18.12.23
Отборочный этап продлён по 24 декабря включительно
Вдоль длинной улицы расположены дома, в каждом из которых живёт по одному человеку. Каждый из жителей улицы является сторонником одной из двух политических партий: 1 или 2. Каждый день каждый человек общается со всеми своими соседями (с одним соседом, если человек живёт в на краю улицы и с обоими соседями в остальных случаях). За ночь он обдумывает полученную от них информацию, и если оказывается, что двое его соседей являются сторонниками противоположной политической партии, к утру человек меняет свои взгляды.
На ленте записана произвольная последовательность единиц и двоек, соответствующая политическим взглядам жителей улицы в какой-то из дней. Постройте машину Тьюринга, которая преобразует эту строку в строку, соответствующую политическим взглядам жителей улицы на следующий день.
q4 и q6 - основные состояния, q4 обозначает, что предыдущий был за 1, а q6 - что предыдущий был за 2. Если оказывается, что в состоянии q4 мы на том человеке, который за 1, то ни предыдущего, ни его менять не надо и мы просто остаемся в том же состоянии q4 и двигаемся вправо. Если же оказывается, что в состоянии q4 мы на том человеке, который за 2, то его нужно поменять, если следующий за 1, для этого мы переходим в состояние "подозрения" q7 и двигаемся вправо, тогда, если там действительно 1, то мы переходим в состояние q5 и двигаемся влево, а состояние q5 у нас меняет 2 на 1 и двигается вправо в состояние q6, т.к. для следующего человека предыдущий был за 2. Если же в состоянии q7 оказывается, что стоит 2, то предыдущего человека не надо менять, причем того, на котором мы сейчас находимся тоже, т,к, предыдущий тоже за 2, как и он, тогда мы просто двигаемся вправо в состояние q6, т.к. для следующего предыдущий будет за 2. Так же как и для состояний q4 с q7, аналогично определяем команды для состояний q6 с q8, где есть также состояние q3, которое меняет 1 на 2 и двигается вправо на состояние q4. Команды q1 и q2 нужны для того, чтобы разобраться с первым человеком, а в конце, если мы попали на звездочку и у нас есть "подозрение", то последнего человека нужно поменять, а если нет, то не нужно и мы переходим в финальное состояние и машина заканчивает работу,