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

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

Задача 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. Нарушение авторских прав; Мы поможем в написании вашей работы!




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


Практические расчеты на срез и смятие При изучении темы обратите внимание на основные расчетные предпосылки и условности расчета...


Функция спроса населения на данный товар Функция спроса населения на данный товар: Qd=7-Р. Функция предложения: Qs= -5+2Р,где...


Аальтернативная стоимость. Кривая производственных возможностей В экономике Буридании есть 100 ед. труда с производительностью 4 м ткани или 2 кг мяса...

Классификация холодных блюд и закусок. Урок №2 Тема: Холодные блюда и закуски. Значение холодных блюд и закусок. Классификация холодных блюд и закусок. Кулинарная обработка продуктов...

ТЕРМОДИНАМИКА БИОЛОГИЧЕСКИХ СИСТЕМ. 1. Особенности термодинамического метода изучения биологических систем. Основные понятия термодинамики. Термодинамикой называется раздел физики...

Травматическая окклюзия и ее клинические признаки При пародонтите и парадонтозе резистентность тканей пародонта падает...

Потенциометрия. Потенциометрическое определение рН растворов Потенциометрия - это электрохимический метод иссле­дования и анализа веществ, основанный на зависимости равновесного электродного потенциала Е от активности (концентрации) определяемого вещества в исследуемом рас­творе...

Гальванического элемента При контакте двух любых фаз на границе их раздела возникает двойной электрический слой (ДЭС), состоящий из равных по величине, но противоположных по знаку электрических зарядов...

Сущность, виды и функции маркетинга персонала Перснал-маркетинг является новым понятием. В мировой практике маркетинга и управления персоналом он выделился в отдельное направление лишь в начале 90-х гг.XX века...

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