Математическая модель машины Тьюринга

Математическая модель машины Тьюринга имеет вид:

Т=<V_t; Q; D; j; y; x >,

Решение задачи с помощью машины Тьюринга

Дано:

A={a,b}

Условие:

Удвоить слово P

Решение:

Для того, чтобы обозначить конец слова, введём в данный нам алфавит ещё один символ - c.

1) Построение таблицы

2) Построение протокола

q₀ а q₀ аП

q₀ b q₀ bП

q₀ # q₁ cЛ

q₁ а q₁ аЛ

q₁ b q₁ bЛ

q₁ # q₂ #П

q₂ а q₃ #П

q₂ b q₄ #П

q₂ c q₇ #Л

q₃ а q₃ аП

q₃ b q₃ bП

q₃ c q₃ cП

q₃ # q₅ аЛ

q₄ а q₄ аП

q₄ b q₄ bП

q₄ c q₄ cП

q₄ # q₆ bЛ

q₅ а q₅ аЛ

q₅ b q₅ bЛ

q₅ c q₅ cЛ

q₅ # q₂ аП

q₆ а q₆ аЛ

q₆ b q₆ bЛ

q₆ c q₆ cЛ

q₆ # q₂ bП

q₇ а q₈ #П

q₇ b q₉ #П

q₇ # q₁₁ #П

q₈ # q₁₀ аЛ

q₉ # q₁₀ bЛ

q₁₀ # q₇ #Л

q₁₁a q_k a C

q₁₁b q_k b C

q₁₁ # q₁₁# П

3) Построение графа

Граф представлен на следующей странице

Пусть нам дана последовательность ab, тогда имеем следующий вычислительный процесс:

4) Результаты отладки на эмуляторе

Для начала отмечу, что данный эмулятор Машины Тьюринга — это автомат, который управляется таблицей. Строки в таблице соответствуют символам выбранного алфавита A, а столбцы — состояниям автомата Q={q0,q1,…,qM}. В начале работы машина Тьюринга находится в состоянии q₁. Состояние q₀ — это конечное состояние: попав в него, автомат заканчивает работу ( именно поэтому в эмуляторе состояний (q) больше, чем в моих таблице, протоколе, графе).

Пусть нам дано входное слово abba, тогда имеем:

Результаты отладки на эмуляторе машины Тьюринга показываю, что вычислительный процесс преобразования исходного слова в заключительное выполняется верно.

Поиск по сайту: