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