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

↑

▷ Содержание

⇐ ПредыдущаяСтр 3 из 8Следующая ⇒

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

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

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

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

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

Для прикладу розглянемо наступну систему команд машини: q₂a₅ → q₃a₄R і q₃a₁L → q₄a₂.

У ході виконання програми буде реалізовано такий ланцюжок команд: q₂a₅a₁a₂ → a₄q₃a₁a₂ → q₄a₄a₂a₂ і отримано наступний результат: q₂a₅a₁a₂ → q₄a₄a₂a_2.

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

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

2 Ліва частина першої команди: q₂a₅ → q₃a₄R, означає, що головка вказує на клітинку, в якій записано символ a_5, якщо головка перебуває в стані q₂ (q₂a₅). В ході виконання команди в стані q₃ в цю саму клітинку замість символа a₅ буде записано символ a₄, після чого головка переміститься вправо і вкаже на символ а₁.

3 Друга команда: q₃a₁L → q₄a₂, означає, що за перебування в стані q₃ головка вказує на клітинку з символом a₁, який за перебування головки в стані q₄ замінюється на символ a₂, після чого головка переміщується вліво.

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

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

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

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

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

Познавательные статьи:



Алгоритмические операторы Matlab

Конструирование и порядок расчёта дорожной одежды

Исследования учёных: почему помогают молитвы?

Почему терпят неудачу многие предприниматели?