Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Представлення МТ сукупністю команд
Кожна команда машини містить не більше однієї дії. Фактично команди виглядають так: – у клітинку, що оглядається, записати символ ai, переміститися вправо (до наступної клітинки) та перейти в стан qj; – у клітинку, що оглядається, записати символ ai, переміститися вліво (до наступної клітинки) та перейти в стан qj; aiS qj – у клітинку, що оглядається, записати символ ai, зупинитися та перейти в стан qj. Наприклад, конфігурацію із внутрішнім станом qi, у якій на стрічці записано слово abcde, а головка вказує на символ d, можна записати у вигляді: abc qi de. Стандартною початковою конфігурацією назвемо конфігурацію вигляду q1α, тобто конфігурацію, що містить початковий стан, в якому головка вказує на крайній лівий символ слова, написаного на стрічці. Аналогічностандартною заключною конфігурацієюназвемо конфігурацію вигляду qk β. Для прикладу розглянемо наступну систему команд машини: q2a5 → q3a4R і q3a1L → q4a2. У ході виконання програми буде реалізовано такий ланцюжок команд: q2a5a1a2 → a4q3a1a2 → q4a4a2a2 і отримано наступний результат: 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}. Якщо, наприклад, початкова конфігурація має вигляд q0 110011, то кінцева конфігурація після завершення операції інвертування повинна мати наступний вигляд qk 001100. Для розв’язання задачі машиною буде створена наступна послідовність команд:
У стандартній початковій конфігурації головка стоїть над першим символом зліва, пристрій управління знаходиться в початковому стані. На наступному такті МТ, не змінюючи свого стану, замінює символ 0 на символ 1 або 1 на 0 і зсувається вправо на один символ. Після перегляду всього ланцюжка виявиться, що головка вказує на символ, який означає порожню клітинку. У цьому випадку машина Тьюринга переходить у новий стан і зсувається вліво на один символ. На подальших тактах управляючий пристрій не змінює свого стану, залишає без зміни символ, на який вказує головка і переміщується вліво до тих пір, поки не натрапить на порожню клітинку, після чого МТ переходить в кінцевий стан і переміщується вправо на один символ, переходячи в стандартну заключну конфігурацію.
|
|||||
Последнее изменение этой страницы: 2017-02-08; просмотров: 301; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 54.87.90.21 (0.005 с.) |