Последние новости
04.09.24
Объявление
09.06.24
Результаты Олимпиады
03.04.24
Предварительные результаты финального тура
05.03.24
Проведение финального тура
01.01.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 нужны для того, чтобы разобраться с первым человеком, а в конце, если мы попали на звездочку и у нас есть "подозрение", то последнего человека нужно поменять, а если нет, то не нужно и мы переходим в финальное состояние и машина заканчивает работу,