Механическое удерживание земляных масс: Механическое удерживание земляных масс на склоне обеспечивают контрфорсными сооружениями различных конструкций...
Типы оградительных сооружений в морском порту: По расположению оградительных сооружений в плане различают волноломы, обе оконечности...
Топ:
Характеристика АТП и сварочно-жестяницкого участка: Транспорт в настоящее время является одной из важнейших отраслей народного хозяйства...
Оснащения врачебно-сестринской бригады.
Процедура выполнения команд. Рабочий цикл процессора: Функционирование процессора в основном состоит из повторяющихся рабочих циклов, каждый из которых соответствует...
Интересное:
Средства для ингаляционного наркоза: Наркоз наступает в результате вдыхания (ингаляции) средств, которое осуществляют или с помощью маски...
Как мы говорим и как мы слушаем: общение можно сравнить с огромным зонтиком, под которым скрыто все...
Финансовый рынок и его значение в управлении денежными потоками на современном этапе: любому предприятию для расширения производства и увеличения прибыли нужны...
Дисциплины:
2019-11-11 | 184 |
5.00
из
|
Заказать работу |
|
|
Машина Тьюринга работает следующим образом. Головка, передвигаясь вдоль ленты, печатает или стирает (т.е. печатает «пустой» символ) символы в ячейках ленты. Эта работа производится по инструкции определенного вида, называемой программой (алгоритмом).
Программа (алгоритм) для машины Тьюринга записывается в виде таблицы, где первые столбец и строка содержат возможные состояния головки (внутренний алфавит) и символы внешнего алфавита. Содержимое таблицы представляет собой команды (элементарные действия) для машины Тьюринга. Команда определяется пересечением символов внутреннего и внешнего алфавитов в таблице. Символ, который обозревает (воспринимает) головка в ячейке ленты (над которой она находится в данный момент) и состояние головки определяют, какую команду нужно выполнить (рис. 2).
Q\S | … | … | ||||
… | ||||||
D | ||||||
… | ||||||
Рис. 2
Одна команда для машины Тьюринга представляет собой конкретную комбинацию трех составляющих: указаний, какой символ записать в ячейку ленты, над которой находится головка, куда передвинуться и в какое состояние перейти.
Для записи команды используется выражения вида D , где - символ который головка должна записать в обозреваемую ячейку, D (D {L,R,N}) – один из трех вариантов сдвига головки: L (Left) – на одну ячейку влево, R (Right) – на одну ячейку вправо, N (None) – остаться на месте (не совершать перехода), – перейти в новое состояние (или остаться в текущем).
Машина Тьюринга, выполняя каждую отдельную команду, осуществляет элементарное действие, называемое шагом (тактом). На каждом отдельном шаге (такте) команда предписывает лишь замену единственного символа , хранящегося в обозреваемой ячейке каким либо другим символом . При i=j содержимое обозреваемой ячейки не изменяется. При переходе от одного шага (такта) к другому адрес обозреваемой ячейки может изменяться не более чем на одну единицу, т.е. обозревается соседняя слева или соседняя справа ячейка, или же обозревается та же ячейка, что и в предыдущем шаге (такте). Таким образом, за один шаг (такт) работы машина Тьюринга может:
|
1. Изменить содержимое обозреваемой ячейки ленты, т.е. заменить содержащийся в ней символ другим, или оставить прежний символ.
2. Совершить сдвиг влево или вправо, или остаться на месте;
3. Перейти в новое состояние, или остаться в текущем состоянии.
Перед запуском машины Тьюринга, необходимо выполнить следующие условия:
1. Задать внешний алфавит и записать в соответствии с ним символы на ленту;
2. Задать начальное положение головки на ленте;
3. Задать начальное состояние головки;
4. Задать некоторую программу (алгоритм), на основании которой головка будет совершать действия.
Правильно составленный алгоритм должен обеспечивать однозначность его понимания и механическое исполнение при всех значениях исходных данных и обладать набором следующих свойств:
1. Дискретность алгоритма: решение задачи, записанное в виде алгоритма, должно быть разбито на отдельные простейшие команды, расположенные в порядке их выполнения;
2. Определённость алгоритма: каждая команда алгоритма должна быть понятна исполнителю, не оставлять места для её неоднозначного толкования и неопределенного исполнения;
3. Результативность алгоритма: алгоритм всегда должен приводить к определенному решению через конечное, минимальное число шагов (или сообщать, что такого решения нет);
4. Массовость алгоритма: каждый алгоритм, разработанный для решения некоторой задачи, должен быть решением и для задач этого типа при всех допустимых значениях исходных данных.
|
II. НЕКОТОРЫЕ ПРАКТИЧЕСКИЕ ПРИМЕРЫ ПРОГРАММ (АЛГОРИТМОВ) ДЛЯ МАШИНЫ ТЬЮРИНГА
|
|
Археология об основании Рима: Новые раскопки проясняют и такой острый дискуссионный вопрос, как дата самого возникновения Рима...
Типы сооружений для обработки осадков: Септиками называются сооружения, в которых одновременно происходят осветление сточной жидкости...
Семя – орган полового размножения и расселения растений: наружи у семян имеется плотный покров – кожура...
Биохимия спиртового брожения: Основу технологии получения пива составляет спиртовое брожение, - при котором сахар превращается...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!