Индивидуальные очистные сооружения: К классу индивидуальных очистных сооружений относят сооружения, пропускная способность которых...
Своеобразие русской архитектуры: Основной материал – дерево – быстрота постройки, но недолговечность и необходимость деления...
Топ:
Основы обеспечения единства измерений: Обеспечение единства измерений - деятельность метрологических служб, направленная на достижение...
Комплексной системы оценки состояния охраны труда на производственном объекте (КСОТ-П): Цели и задачи Комплексной системы оценки состояния охраны труда и определению факторов рисков по охране труда...
Интересное:
Средства для ингаляционного наркоза: Наркоз наступает в результате вдыхания (ингаляции) средств, которое осуществляют или с помощью маски...
Национальное богатство страны и его составляющие: для оценки элементов национального богатства используются...
Подходы к решению темы фильма: Существует три основных типа исторического фильма, имеющих между собой много общего...
Дисциплины:
 2019-11-19 |
 178 |
из
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 является конечным состоянием. Работа машины Тьюринга останавливается.
Диаграмма переходов машины Тьюринга для заданных начальных условий и таблицы функционирования имеет вид:
|
|
|
История создания датчика движения: Первый прибор для обнаружения движения был изобретен немецким физиком Генрихом Герцем...
Архитектура электронного правительства: Единая архитектура – это методологический подход при создании системы управления государства, который строится...
История развития пистолетов-пулеметов: Предпосылкой для возникновения пистолетов-пулеметов послужила давняя тенденция тяготения винтовок...
Папиллярные узоры пальцев рук - маркер спортивных способностей: дерматоглифические признаки формируются на 3-5 месяце беременности, не изменяются в течение жизни...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!