Главная Случайная страница


Полезное:

Как сделать разговор полезным и приятным Как сделать объемную звезду своими руками Как сделать то, что делать не хочется? Как сделать погремушку Как сделать так чтобы женщины сами знакомились с вами Как сделать идею коммерческой Как сделать хорошую растяжку ног? Как сделать наш разум здоровым? Как сделать, чтобы люди обманывали меньше Вопрос 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: 290; Нарушение авторских прав; Помощь в написании работы --> СЮДА...



mydocx.ru - 2015-2024 year. (0.009 sec.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав - Пожаловаться на публикацию