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