Постройте машину Тьюринга перерабатывающую слово 01x01y в слово 01x01y01x01y. Бесплатный доступ к решению задач

Реферат.Справочник
Решенные задачи по другому
Постройте машину Тьюринга перерабатывающую слово 01x01y в слово 01x01y01x01y

Постройте машину Тьюринга перерабатывающую слово 01x01y в слово 01x01y01x01y .pdf

Зарегистрируйся в 2 клика в Кампус и получи неограниченный доступ к материалам с подпиской Кампус+ 🔥

Условие

Постройте машину Тьюринга, перерабатывающую слово 01x01y в слово 01x01y01x01y, причем в начальном положении обозревается самая левая ячейка, а в конечном – ячейка, в которой записан 0, заключенный между массивами 1x01y и 1x01y. (Машина называется «копирование» и обозначается K2).

Нужно полное решение этой работы?

Решение

Потяни, чтобы посмотреть

Пусть внешний алфавит машины Тьюринга A={a0, 0,1}.
Состояний у машины будет шестнадцать: q0 – остановка, q1, …, q15 – рабочие состояния, т.е. Q={q0, q1, …, q15}.
Функциональная схема (программа) машины:
q10 → q20П,
q2 0 → q9 0П, q2 1 → q3 a0П,
q3 0 → q4 0П, q3 1 → q3 1П,
q4 0 → q5 0П, q4 1 → q4 1П, q4 a0 → q5 0П,
q5 1 → q5 1П, q5 a0 → q6 1Л,
q6 0 → q7 0Л, q6 1 → q6 1Л,
q7 0 → q8 0Л, q7 1 → q7 1Л,
q8 1 → q8 1Л, q8 a0 → q2 1П,
q9 0 → q0 0, q9 1 → q10 a0 П,
q10 0 → q11 0П, q10 1 → q10 1П,
q11 0 → q12 0П, q11 1 → q11 1П, q11 a0 → q12 0П,
q12 1 → q12 1П, q12 a0 → q13 1Л,
q13 0 → q14 0Л, q13 1 → q13 1Л,
q14 0 → q15 0Л, q14 1 → q14 1Л,
q15 1→ q15 1Л, q15 a0 → q9 1П.
В начальном положении обозревается самая левая ячейка.
Приведем последовательность конфигураций, получаемых при переработке этой машиной слова 0110111 (012013):
q10110111 → 0 q2110111 → 0 a0 q310111 → 0a01q30111 → 0a010 q4111
→ 0a010 1 q411→ 0a01011q41→ 0a010111 q4 a0→ 0a010111 0 q5 a0
→ 0a010111 q6 01→ 0a01011 q7101→ 0a0101 q71101→ 0a010 q711101
→ 0a01 q7011101→ 0a0 q81011101→ 0 q8a0 1011101→ 01q21011101
→ 01 a0 q3011101→…→ 011q20111011→ 0110 q9111011
→ 0110 a0 q10 11011→ 0110 a01q101011→ 0110 a011 q10011
→ 0110 a0110 q1111→ 0110 a01101 q111→ 0110 a011011 q11 a0
→ 0110 a0110110q12 a0→ 0110 a011011 q1301→ 0110 a01101 q14101
→ 0110 a0110 q141101→ 0110 a011 q1401101→ 0110 a01 q15101101
→ 0110 a0 q151101101→ 0110 q15 a01101101→ 0110 1 q91101101
→ 0110 1 a0 q10 101101 →…→ 011011q15 a00110111→ 0110111q9 0110111
→ 0110111q0 0110111.

50% задачи недоступно для прочтения

Переходи в Кампус, регистрируйся и получай полное решение

Получить задачу