Задание для машины Тьюринга.

[skDYLAN]

Дано двоичное число, содержащее 2n разрядов. Зеркально
отразить цифры числа относительно середины. Начальное
положение каретки – над крайней правой цифрой числа.

Зеркально отразить все число проблем не составит, но относительно его середины надо. Как вообще найти середину числа в Тьюринге.

[llll14]

слушал лекцию на немецком, так что терминология может отличаться.
Если лента одна и не ограничена со сторон, то я бы сделал так:
копируем слово, чтобы остался оригинал.
M = (Q, Sigma, Gamma, delta, qstart, blank, qend)
чтобы найти середину слова (2n=четное), начинаем в правом углу:
1) если справа blank, то пишем blank и идем влево пока не встретим blank, шаг вправо и затираем левый бит - пишем blank, то есть удалили самый крайний левый и правый бит
2) теперь надо записать, что удалили 2 бита:
идем вправо до blank, ну и например шаг вправо и пишем 1
3) повторяем цыкл с 1)
пример: bbb110011bbb
1) bbbb1001bbbb1
2) bbbbb00bbbbb11
3) bbbbbbbbbbbb111
То есть середина данного числа - 3 бита от начала
Ну и естественно раскидать алгоритм по состояниям

[skDYLAN]

Блин.. то что нашел середину особого продвижения не дало.

Что можно дальше придумать....