Типы сооружений для обработки осадков: Септиками называются сооружения, в которых одновременно происходят осветление сточной жидкости...
Кормораздатчик мобильный электрифицированный: схема и процесс работы устройства...
Топ:
Оценка эффективности инструментов коммуникационной политики: Внешние коммуникации - обмен информацией между организацией и её внешней средой...
Проблема типологии научных революций: Глобальные научные революции и типы научной рациональности...
Выпускная квалификационная работа: Основная часть ВКР, как правило, состоит из двух-трех глав, каждая из которых, в свою очередь...
Интересное:
Отражение на счетах бухгалтерского учета процесса приобретения: Процесс заготовления представляет систему экономических событий, включающих приобретение организацией у поставщиков сырья...
Инженерная защита территорий, зданий и сооружений от опасных геологических процессов: Изучение оползневых явлений, оценка устойчивости склонов и проектирование противооползневых сооружений — актуальнейшие задачи, стоящие перед отечественными...
Распространение рака на другие отдаленные от желудка органы: Характерных симптомов рака желудка не существует. Выраженные симптомы появляются, когда опухоль...
Дисциплины:
2019-11-19 | 243 |
5.00
из
|
Заказать работу |
|
|
(4 неделя, 2 часа)
Рассмотрим устройство, которое состоит из бесконечной в оба конца ленты и автомата. Лента разбита на ячейки, в которые вписываются символы из внешнего алфавита { , a0, a1,..., aN}, причем символ " " означает пустой символ. Автомат может находиться в одном из состояний {q1,..., qr} и осуществлять одно из трех движений в каждый момент времени, {R, L, S}: R - переместиться на одну ячейку вправо, L - переместиться на одну ячейку влево, S - остаться на месте. Работу такого устройства можно задать с помощью специальной таблицы, называемой программой.
В самом левом столбце располагаются символы алфавита { , a0, a1,..., aN} (внешний алфавит машины). Множество {q1,..., qr} - внутренний алфавит машины. Некоторые клетки этой таблицы могут быть пустыми. В клетки этой таблицы записываются команды машины, т.е. тройки символов cDq, где c - символ из внешнего алфавита машины, q - символ из внутреннего алфавита машины и D - символ из алфавита, описывающего движение, т.е. из множества {R, L, S}. Если в некоторый момент времени головка автомата обозревает на ленте символ a i и автомат находится в состоянии q j, то машина должна выполнить команду, стоящую на пересечении строки с номером a i и столбца с номером q j. Если в означенной клетке находится команда cDq, то машина должна записать в текущую ячейку символ c, перейти в состояние q и осуществить движение D. Если означенная клетка окажется пустой, то машина останавливается.
q1 | qj | qr | |
a0 | |||
a1 | |||
. | |||
. | |||
. | |||
ai | cDq | ||
. | |||
. | |||
. | |||
aN |
Конфигурацией машины Тьюринга называется цепочка вида a qa b, где a a b - содержимое ленты, q - текущее состояние головки, а её позиция указывает обозреваемую ячейку между a и b (см. рисунок). Пишем ax для сокращения слова . Предполагается, что начальная конфигурация всегда имеет вид q 0 a b, т.е. головка в этих конфигурациях всегда сдвинута к левому концу ленты. В результате применения программы возможны 2 ситуации:
|
1. В некоторый момент времени появится пустая команда (или пустая клетка) и машина остановится.
Пример 3.
Добавить 1 к унарному числу посредством машины Тьюринга.
Внешний алфавит может быть задан множеством A ={ ,1}, где 1 соответствует заполненной секции, а - пустому знаку, причем заполненные следуют друг за другом подряд. Внутренний алфавит задается множеством Q ={ q, z }, где q соответствует рабочему состоянию логического устройства, а z – остановке. Набор всех правил преобразования (логическая функция) может быть представлен функциональной схемой:
A | q | z |
z 1 S | z S | |
1 | q 1 R | z 1 S |
Составляется функциональная схема в виде таблицы таким образом, что знаки, обозначающие колонки и строки, определяют входные параметры логического устройства, а в ячейке таблицы на их пересечении стоит выходная команда. В частности, если головка машины обозревает секцию ленты со знаком 1 и машина находится в рабочем состоянии (q), то результатом её работы на данном такте должно стать повторение 1 в данной секции и переход на одну секцию вправо R - эта команда записывается как q 1 R. Если же в обозреваемой секции , а состояние логического устройства (ЛУ) q, то будет заменён 1, сдвига ленты производиться не будет и машина остановится - z 1 S.
Пусть начальной является конфигурация 1 q 1111. Тогда работа машины в соответствии с описанной логической функцией будет происходить следующим образом:
Такт 1. Обозревается 1, в ЛУ состояние q. Выходная команда q 1 R, что эквивалентно перемещению головки по отношению ленты на 1 шаг вправо. Следовательно, образуется промежуточная конфигурация 11 q 111.
|
Такт 2. Аналогичным образом осуществляется переход к конфигурации 111 q 11.
Такт 3. Переход к конфигурации 1111 q 1.
Такт 4. Переход к конфигурации 11111 q .
Такт 5. Обозревается , в ЛУ состояние q. Выходная команда z 1 S – вместо в ячейку записывается 1, сдвига нет, работа прекращается.
Конечная конфигурация 111111 z.
Пример 4.
Имеется запись многоразрядного числа n в десятичной системе счисления. Построить машину Тьюринга, которая обеспечивала бы вычисление значения n +1.
Используем внешний алфавит А ={0,1,…,9,0, }, в котором символ соответствует пустому знаку. Внутренний алфавит, как и в предыдущем примере, образуется двумя состояниями – рабочим (q) и остановкой (z) (Q ={ q, z }). Исходное число n, а также результат – n +1 – записываются в десятичной системе, причем, цифры размещаются по одной в соседних ячейках без пропусков. Функциональную схему представим таблицей:
a | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
q | z 1 S | z 2 S | z 3 S | z 4 S | z 5 S | z 6 S | z 7 S | z 8 S | z 9 S | q 0 L | z 1 S |
Пусть начальной конфигурацией будет 21 q 9.
Такт 1. q 9 q 0 L, т.е. 9 будет замещена на 0 и головка сдвинется на разряд десятков – промежуточная конфигурация 2 q 10.
Такт 2. q 1 z 2 S, т.е. 1 будет заменена на 2 и произойдет остановка с конечной конфигурацией 2 z 20, т.е. получен результат сложения 219+1.
Пусть начальной конфигурацией будет 99 q 9.
Такт 1. q 9 q 0 L, т.е. сформируется промежуточная конфигурация 9 q 90.
Такт 2. q 9 q 0 L, возникнет конфигурация q 900.
Такт 3. q 9 q 0 L, возникнет q 000.
Такт 4. q z 1 S – возникнет z 1000 и работа прекращается.
Задания
|
|
Адаптации растений и животных к жизни в горах: Большое значение для жизни организмов в горах имеют степень расчленения, крутизна и экспозиционные различия склонов...
Двойное оплодотворение у цветковых растений: Оплодотворение - это процесс слияния мужской и женской половых клеток с образованием зиготы...
Общие условия выбора системы дренажа: Система дренажа выбирается в зависимости от характера защищаемого...
История развития пистолетов-пулеметов: Предпосылкой для возникновения пистолетов-пулеметов послужила давняя тенденция тяготения винтовок...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!