Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Задача 11.





а) Покажите, что операция композиции машин ассоциативна, т.е. для любых машин M1, M2, M3

(M1°М2)°М3 = М1°(М2°М3).

б) Является ли операция композиции машин коммутативной?

 

Окончательно машину из примера 9 мы можем записать: С°А°А°А или С°А3, если условиться считать

Даны 3 машины М1, М2, М3, имеющие общий алфавит А = {s0, s1, s2,..., sk} и состояния q0, q1,..., qp; q'0, q'1,..., q'm; q''0, q''1,..., q''n соответственно. Ветвлением машин M1, M2, М3 называется машина, обозначаемая имеющая алфавит А и состояния q0, q1, q2,..., qp, qp+1, q'1,..., q'm, q''1, q''2,..., q''n. Программа этой машины строится из программ машин M1, M2, M3 так, как показано в следующей таблице:

 

программа машины М3, заключительное состояние которой q''0 заменено на q0
программа машины М2, заключительное состояние которой q'0 заменено на q0
команда условного перехода
программа машины M1, заключительное состояние которой q0 заменено на состояние qp+1

 

Проиллюстрируем теперь программу машины из примера 10 (табл. 16).

 

 

Таблица 16

  s0 |
q1 s0Лq2 |Лq2
q2 s0Нq3 |Нq6
q3 s0Пq4 |Пq4
q4 s0Пq5 |Пq4
q5 |Нq0  
q6 s0Пq7 |Пq7
q7 s0Пq8 |Пq7
q8 |Нq9  
q9 |Нq0 |Пq9

 

Программа машины из примера 10 запишется, как видно, следующим образом: , где M1, M2, М3 указаны слева от программы.

Дальнейший анализ программы машины из примера 10 показывает, что машина M1— это машина l, машину М2 можно представить в виде композиции машин r и С (r°С), а М3— в виде r°С°А. Тогда машина из примера 10 окончательно запишется так:

Как видно, из простых (элементарных) машин Тьюринга l, r, С, А с помощью операций композиции и ветвления сконструировали более сложную машину Тьюринга (пример 10).

Дана машина М, имеющая алфавит А={s0, s1, s2,..., sk} и состояния q0, q1, …, qp. Программа машины М содержит по крайней мере две команды с заключительным состоянием q0. Будем говорить, что машина М' получена из машины М с помощью операции зацикливания, если в одной из команд машины М, содержащих состояние q0, это состояние заменено на одно из состояний q1, q2, …, qp.

 

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

Таблица 17

  s0 |
q1 s0Лq2 |Лq1
q2 q3 q6
q3 s0Пq4  
q4 s0Пq4 |Пq5
q5 s0Лq0 |Пq5
q6 s0Нq0 s0Лq6

Действительно, эта программа содержит две команды с заключительным состоянием q0: s0Лq0 и s0Нq0. Заменив в команде s0Нq0 состояние q0 состоянием q1 получили машину из примера 11.

 

Проанализируем теперь программу этой машины, данную в таблице 18.

 

Таблица 18

  s0 |
q1 s0Лq2 |Лq1
q2 q3 q6
q3 s0Пq4  
q4 s0Пq4 |Пq5
q5 s0Лq0 |Пq5
q6 s0Нq1 s0Лq6

 

Работа этой машины может быть следующим образом описана в терминах машин Р, Q, R. Сначала используется машина Р, затем в соответствии с тем, обозревает машина Р в состоянии q2 пустую ячейку или ячейку с буквой |, используется машина R или Q соответственно. В случае если используется машина Q, ее результат подается в Р. Записать это можно следующим образом: , где точки обозначают, что результат работы машины Q подается обратно в качестве входных данных для машины Р.







Дата добавления: 2015-09-07; просмотров: 428. Нарушение авторских прав; Мы поможем в написании вашей работы!




Кардиналистский и ординалистский подходы Кардиналистский (количественный подход) к анализу полезности основан на представлении о возможности измерения различных благ в условных единицах полезности...


Обзор компонентов Multisim Компоненты – это основа любой схемы, это все элементы, из которых она состоит. Multisim оперирует с двумя категориями...


Композиция из абстрактных геометрических фигур Данная композиция состоит из линий, штриховки, абстрактных геометрических форм...


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

Опухоли яичников в детском и подростковом возрасте Опухоли яичников занимают первое место в структуре опухолей половой системы у девочек и встречаются в возрасте 10 – 16 лет и в период полового созревания...

Способы тактических действий при проведении специальных операций Специальные операции проводятся с применением следующих основных тактических способов действий: охрана...

Искусство подбора персонала. Как оценить человека за час Искусство подбора персонала. Как оценить человека за час...

Хронометражно-табличная методика определения суточного расхода энергии студента Цель: познакомиться с хронометражно-табличным методом опреде­ления суточного расхода энергии...

ОЧАГОВЫЕ ТЕНИ В ЛЕГКОМ Очаговыми легочными инфильтратами проявляют себя различные по этиологии заболевания, в основе которых лежит бронхо-нодулярный процесс, который при рентгенологическом исследовании дает очагового характера тень, размерами не более 1 см в диаметре...

Примеры решения типовых задач. Пример 1.Степень диссоциации уксусной кислоты в 0,1 М растворе равна 1,32∙10-2   Пример 1.Степень диссоциации уксусной кислоты в 0,1 М растворе равна 1,32∙10-2. Найдите константу диссоциации кислоты и значение рК. Решение. Подставим данные задачи в уравнение закона разбавления К = a2См/(1 –a) =...

Studopedia.info - Студопедия - 2014-2025 год . (0.014 сек.) русская версия | украинская версия