Не знал в каком топике отпостить. Помогите пожалуйста записать алгоритм для машины Тьюринга.
Переставить в 8ми битном слове старшие и младшие 4 бита.
Алгоритм вроде как надо сохранить старшие или младшие 4 бита, затем поменять перепасать в сохраненную область оставшиеся 4 бита и на другое место записать сохраненные биты. Помогите записать сами команды для машины Тьюринга. Ну типа такого:
q0 0 -> q1 (лямбда) R

Например:
10010110
Сохраним 0110 (младшие 4 бит).
Запишем 1001 на место 0110.
Запишем из сохренной области на место старших бит

Во-первых, переношу тему в раздел "Алгоритмы"
Во-вторых, не совсем понятно, что тебе все же нужно. По сути, ты уже написал сам алгоритм (при условии, что есть свободное место для копирования четырех бит. Вопрос в том - можно ли использовать это свободное место или надо обойтись без него?

Свободное место на ленте есть! Считается что она бесконечна.

По сути мне нужна конкретная таблица переходов. Просто мне не совсем понятно, в примере сохранения у меня присутствует следующая запись:
(Здесь за L обозначим лямбда)
Q0 1 -> Q1 L R
Q0 0 -> Q2 L R
Мне нужна вся таблица таких переходов. А конкретно не понятно следующее: есть состояние Q0, если в нем содержится 1 то пишем в состояние 1(ну или за границу 8 бит), если 0 то в другое. Как для переноса эти состояния записать?

В состояниях ничего не содержиться...машина тьюринга состоит из головки и бесконечной ленты...это головка может находиться в различных состояниях q1 q2 q3 (q0-конечное)...и это головка передвигаеться по ленте...
смотря в каком состоянии головка и что находиться на ленте выбираеться нужное действие...
запись q1L->1Rq2 озночает, что если головка находиться в состоянии q1 попадает на ленту в ячейке которой написано L, то L заменяеться на 1...головка принимает состояние q2 и движеться вправо...

Алгоритм немного другой так как сохранить 4 бита негде...так что придёться переносить по символу в конец слова...и удалять символ который мы переносим...

На рисунке реализован перенос 1-го бита...чтобы перенести 4 надо по аналогии длописать несколько строк...думаю разберёшься...(в столбике состояние,в строке алфавит,на пересечении результа)

Нажмите для просмотра прикрепленного файла