ТОП 10:

Представлення МТ сукупністю команд



Кожна команда машини містить не більше однієї дії. Фактично команди виглядають так:

– у клітинку, що оглядається, записати символ ai, переміститися вправо (до наступної клітинки) та перейти в стан qj;

– у клітинку, що оглядається, записати символ ai, переміститися вліво (до наступної клітинки) та перейти в стан qj;

aiS qj – у клітинку, що оглядається, записати символ ai, зупинитися та перейти в стан qj.

Наприклад, конфігурацію із внутрішнім станом qi, у якій на стрічці записано слово abcde, а головка вказує на символ d, можна записати у вигляді: abcqide. Стандартною початковою конфігурацією назвемо конфігурацію вигляду q1α, тобто конфігурацію, що містить початковий стан, в якому головка вказує на крайній лівий символ слова, написаного на стрічці. Аналогічностандартною заключною конфігурацієюназвемо конфігурацію вигляду qk β.

Для прикладу розглянемо наступну систему команд машини: q2a5 → q3a4R і q3a1L → q4a2.

У ході виконання програми буде реалізовано такий ланцюжок команд: q2a5a1a2a4q3a1a2q4a4a2a2 і отримано наступний результат: q2a5a1a2 → q4a4a2a2.

Далі наведемо пояснення щодо роботи прикладу.

1 На інформаційній стрічці в трьох клітинках записано слово а5 а1 а2.

2 Ліва частина першої команди: q2a5 → q3a4R, означає, що головка вказує на клітинку, в якій записано символ a5, якщо головка перебуває в стані q2 (q2a5). В ході виконання команди в стані q3 в цю саму клітинку замість символа a5 буде записано символ a4, після чого головка переміститься вправо і вкаже на символ а1.

3 Друга команда: q3a1L → q4a2, означає, що за перебування в стані q3 головка вказує на клітинку з символом a1, який за перебування головки в стані q4 замінюється на символ a2, після чого головка переміщується вліво.

У результаті виконання послідовності команд отримано наступну конфігурацію МТ: q4a4a2a2.

В якості другого прикладу розглянемо сукупність команд МТ, яка інвертує вхідний ланцюжок, записаний з використанням нулів і одиниць.

Нехай алфавіт машини Тьюринга задано множиною: A = {0, 1, ε}, де символ ε відповідає порожній клітинці, а число станів пристрою управління задано в вигляді множини: Q = {q0, q1, qk}.

Якщо, наприклад, початкова конфігурація має вигляд q0110011, то кінцева конфігурація після завершення операції інвертування повинна мати наступний вигляд qk001100. Для розв’язання задачі машиною буде створена наступна послідовність команд:

q01 → q00R, q10 → q10L,q00 → q01R, q11 → q11L,q0 ε → q1εL, q1ε → qkεR.

У стандартній початковій конфігурації головка стоїть над першим символом зліва, пристрій управління знаходиться в початковому стані. На наступному такті МТ, не змінюючи свого стану, замінює символ 0 на символ 1 або 1 на 0 і зсувається вправо на один символ. Після перегляду всього ланцюжка виявиться, що головка вказує на символ, який означає порожню клітинку. У цьому випадку машина Тьюринга переходить у новий стан і зсувається вліво на один символ. На подальших тактах управляючий пристрій не змінює свого стану, залишає без зміни символ, на який вказує головка і переміщується вліво до тих пір, поки не натрапить на порожню клітинку, після чого МТ переходить в кінцевий стан і переміщується вправо на один символ, переходячи в стандартну заключну конфігурацію.

 







Последнее изменение этой страницы: 2017-02-08; Нарушение авторского права страницы

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 34.207.152.62 (0.003 с.)