Механическое удерживание земляных масс: Механическое удерживание земляных масс на склоне обеспечивают контрфорсными сооружениями различных конструкций...
Автоматическое растормаживание колес: Тормозные устройства колес предназначены для уменьшения длины пробега и улучшения маневрирования ВС при...
Топ:
Эволюция кровеносной системы позвоночных животных: Биологическая эволюция – необратимый процесс исторического развития живой природы...
Оценка эффективности инструментов коммуникационной политики: Внешние коммуникации - обмен информацией между организацией и её внешней средой...
Интересное:
Влияние предпринимательской среды на эффективное функционирование предприятия: Предпринимательская среда – это совокупность внешних и внутренних факторов, оказывающих влияние на функционирование фирмы...
Инженерная защита территорий, зданий и сооружений от опасных геологических процессов: Изучение оползневых явлений, оценка устойчивости склонов и проектирование противооползневых сооружений — актуальнейшие задачи, стоящие перед отечественными...
Принципы управления денежными потоками: одним из методов контроля за состоянием денежной наличности является...
Дисциплины:
2019-11-19 | 180 |
5.00
из
|
Заказать работу |
|
|
Способы задания работы машины Тьюринга могут быть описаны как: табличным способом, аналитическим и графическим.
Табличный способ записи логической функции осуществляется при помощи таблицы, строки которой являются символами алфавита S, столбцы – состояния машины Тьюринга из множества Q, а на пересечении – символ состояния, записываемый символ, направление сдвига головки.
q1 | q2 | ….. | qr | |
S1 | ||||
S2 | q8S1L | |||
……. | ||||
Sk |
Аналитический способ записи логической функции осуществляется с помощью системы Тьюринговых команд, которые составляются на основании таблицы, или уже готовый системы команд. Например, запись логической функции, соответствующая таблице .
Графический способ записи логической функции называется диаграммой (графом) переходов. Вершинами графа являются состояния машины Тьюринга из множества состояний Q, ребрами графа – команды перехода из состояния в состояние с указанием записываемого символа и направления сдвига головки.
Осуществляется переход из состояния q2 в состояние q8, в ячейку будет записан символ алфавита S1, головка сдвинута влево на одну позицию.
Работа машины Тьюринга. Тьюрингово вычисление
Работа машины Тьюринга.
Пусть задана МТ с алфавитом S = {1, á, â, ë} и состояниями Q = {q1, q2, q3, q4, q5}. Перед началом работы на ленту заносится начальная информация (например, пять 1) и фиксируется начальная обозреваемая ячейка (например,4). Работа описывается таблицей:
q1 | q2 | q3 | q4 | q5 | |
ë | q4 áR | q3 áL | q1áR | q5 ëL | q5 ëE |
1 | q2 áE | q1âE | q11R | q5 ëR | q5 1E |
á | q4 áL | q2 áR | q3 1L | q4ëR | q5 áE |
â | q1âL | q2 âR | q3 áL | q4ëR | q5 âE |
Определить:
|
- Информацию на ленте после останова.
- Записать систему Тьюринговых команд.
- Построить блок-схему работы МТ.
Изобразим на ленте начальную информацию и фиксированную ячейку:
Учитывая начальные условия, будем искать в таблице пересечение строки содержащей символ алфавита 1 и состояния q1. Это пересечение равно - q2 áE. Система Тьюринговых команд имеет вид - . Данная запись означает: машина переходит в состояние q2, записывает в 4 ячейку символ алфавита á и оставляет головку на ячейке с номером 4. Теперь будем искать в таблице пересечение строки содержащей символ алфавита á и состояния q2 . Это пересечение равно - q2 áR. Данная запись означает: машина переходит в состояние q2, записывает в 4 ячейку символ алфавита á и переводит головку на ячейке с номером 3 и т.д.
Информация на ленте | Система Тьюринговых команд |
Состояние МТ не меняется, символ в ячейке не меняется, следовательно, состояние q5 является конечным состоянием. Работа машины Тьюринга останавливается.
Диаграмма переходов машины Тьюринга для заданных начальных условий и таблицы функционирования имеет вид:
|
|
Архитектура электронного правительства: Единая архитектура – это методологический подход при создании системы управления государства, который строится...
Адаптации растений и животных к жизни в горах: Большое значение для жизни организмов в горах имеют степень расчленения, крутизна и экспозиционные различия склонов...
Биохимия спиртового брожения: Основу технологии получения пива составляет спиртовое брожение, - при котором сахар превращается...
История развития пистолетов-пулеметов: Предпосылкой для возникновения пистолетов-пулеметов послужила давняя тенденция тяготения винтовок...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!