Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
Композиція машин Т'юринга
|
|
Визначення. Нехай задані машини Т'юринга S 1 і S 2, що мають загальний зовнішній алфавіт { a 0, a 1, …, am } і алфавіти внутрішніх станів { q 0, q 1, …, qn }і 
відповідно. Композицією (чи множенням) машини S 1 на машину S 2 називається нова машина S з тим же зовнішнім алфавітом { a 0, a 1, …, am }, внутрішнім алфавітом { q 0, q 1, …, qn, qn +1, …, qn + t } і програмою, що виходить наступним чином. У всіх командах з S 2 що містять символ q0, залишаємо незмінними, а всі останні стани на 
, змінюємо відповідно на qn + i . Сукупність усіх так отриманих команд утворює програму машини-композиції S.
Введене поняття є зручним інструментом для конструювання машин Т'юринга. Покажемо це на прикладі.
Приклад. Сконструюємо машини Т'юринга, правильно обчислюючі функції-проектори 
.
Розглянемо спочатку конкретний випадок n = 3, m = 2, тобто функцію 
. Ми повинні переробити слово 
в слово 
. Будемо застосовувати до початкової конфігурації послідовно сконструйовані раніше машини Т'юринга Б+, В, Б-, О:
Таким чином, функція 
обчислюється слідуючою композицією машин Б+ВБ+ОБ-ОБ- = Б+ВБ+(ОБ-)2.
Date: 2015-09-24; view: 357; Нарушение авторских прав