Двойное оплодотворение у цветковых растений: Оплодотворение - это процесс слияния мужской и женской половых клеток с образованием зиготы...
История развития хранилищ для нефти: Первые склады нефти появились в XVII веке. Они представляли собой землянные ямы-амбара глубиной 4…5 м...
Топ:
Особенности труда и отдыха в условиях низких температур: К работам при низких температурах на открытом воздухе и в не отапливаемых помещениях допускаются лица не моложе 18 лет, прошедшие...
Оценка эффективности инструментов коммуникационной политики: Внешние коммуникации - обмен информацией между организацией и её внешней средой...
Техника безопасности при работе на пароконвектомате: К обслуживанию пароконвектомата допускаются лица, прошедшие технический минимум по эксплуатации оборудования...
Интересное:
Подходы к решению темы фильма: Существует три основных типа исторического фильма, имеющих между собой много общего...
Как мы говорим и как мы слушаем: общение можно сравнить с огромным зонтиком, под которым скрыто все...
Национальное богатство страны и его составляющие: для оценки элементов национального богатства используются...
Дисциплины:
2019-11-11 | 181 |
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. НЕКОТОРЫЕ ПРАКТИЧЕСКИЕ ПРИМЕРЫ ПРОГРАММ (АЛГОРИТМОВ) ДЛЯ МАШИНЫ ТЬЮРИНГА
|
|
История создания датчика движения: Первый прибор для обнаружения движения был изобретен немецким физиком Генрихом Герцем...
Особенности сооружения опор в сложных условиях: Сооружение ВЛ в районах с суровыми климатическими и тяжелыми геологическими условиями...
Папиллярные узоры пальцев рук - маркер спортивных способностей: дерматоглифические признаки формируются на 3-5 месяце беременности, не изменяются в течение жизни...
Биохимия спиртового брожения: Основу технологии получения пива составляет спиртовое брожение, - при котором сахар превращается...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!