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