История создания датчика движения: Первый прибор для обнаружения движения был изобретен немецким физиком Генрихом Герцем...
Двойное оплодотворение у цветковых растений: Оплодотворение - это процесс слияния мужской и женской половых клеток с образованием зиготы...
Топ:
Основы обеспечения единства измерений: Обеспечение единства измерений - деятельность метрологических служб, направленная на достижение...
Процедура выполнения команд. Рабочий цикл процессора: Функционирование процессора в основном состоит из повторяющихся рабочих циклов, каждый из которых соответствует...
Определение места расположения распределительного центра: Фирма реализует продукцию на рынках сбыта и имеет постоянных поставщиков в разных регионах. Увеличение объема продаж...
Интересное:
Подходы к решению темы фильма: Существует три основных типа исторического фильма, имеющих между собой много общего...
Как мы говорим и как мы слушаем: общение можно сравнить с огромным зонтиком, под которым скрыто все...
Инженерная защита территорий, зданий и сооружений от опасных геологических процессов: Изучение оползневых явлений, оценка устойчивости склонов и проектирование противооползневых сооружений — актуальнейшие задачи, стоящие перед отечественными...
Дисциплины:
2019-11-19 | 151 |
5.00
из
|
Заказать работу |
|
|
Исходные данные и результаты операции являются натуральными числами.
Считаем, что в МТ каждое число задано в виде набора «1» и отделяются друг от друга символом «*». Тогда имеем алфавит S = {1, *, ë}. Состояния заданы множеством Q = {q0, q1, q2, q3, q4}.
Рассмотрим пример сложения двух чисел: 2+2=4. Начальные условия: На ленту записаны пары чисел, разделенные знаком «*», начальное состояние q0 и обозревается крайняя левая единица.
Изобразим начальные установки и информацию на ленте перед началом работы.
Просто убрать «*» нельзя, т.к. на ее месте будет записан пустой символ (пробел или ë), а совокупность единиц с пробелом не является заданием числа натурального ряда.
Для реализации операции сложения используем таблицу функционирования МТ, записанную в сокращенном виде, т.е. опускаем не изменяемые состояния и символы.
q0 | q1 | q2 | |
1 | q2 ëR | L | R |
ë | R | q0R | q11 |
* | !ë | L | R |
Знак «!» означает остановку работы машины Тьюринга.
Рассмотрим работу примера в соответствии с таблицей функционирования и начальными условиями.
Такт работы МТ | Система команд | Информация на ленте |
t1 | ||
t2…t5 | Сдвиг головки машины вправо | |
t6 | ||
t7..t11 | Сдвиг головки машины влево | |
t12 | ||
t13 | ||
t14…t17 | Сдвиг головки машины вправо | |
t18 | ||
t19…t23 | Сдвиг головки машины влево | |
t24 | ||
t25 | ||
t26 | !ë |
Длительность выполнения операции сложения (количество тактов) зависит от длины слагаемых.
Структура машины Поста. Команды машины Поста.
Машина Поста, как и ее близкий родственник – машина Тьюринга – есть математическая (воображаемая) машина. Работа машины происходит, детерминировано, позволяет вводить начальные данные, и после выполнения читать результат.
|
Структура машины Поста.
Машина поста состоит из ленты и каретки (называемой так же считывающей и записывающей головкой).
Лента неограниченна и разделена на одинаковые секции (ячейки). Порядок, в котором расположены секции ленты, подобен порядку, в котором расположены все целые числа. Поэтому естественно ввести на ленте «целочисленную систему координат», пронумеровав секции целыми числами …, -3, -2, -1, 0, 1, 2, 3, … Будем считать, что система координат жестко сопоставлена с лентой, и таким образом, получим возможность указывать какую-либо секцию ленты, называя ее порядковый номер, или координату.
В каждой секции ленты может быть либо ничего не записано (такая секция называется пустой), либо записана метка V (тогда секция называется отмеченной).
Информация о том, какие секции пусты, а какие отмечены, образуют состояние ленты.
Каретка может передвигаться вдоль ленты влево и вправо. Когда она неподвижна, она стоит против одной секции ленты, говорят, что каретка обозревает эту секцию, или держит ее в поле зрения.
Информация о том, какие секции пусты, а какие отмечены и где стоит каретка, образует состояние машины Поста. За единицу времени (называемую шагом) каретка может поставить (напечатать) или уничтожить (стереть) метку в той секции, против которой она стоит, а так же распознать, стоит или нет метка в обозреваемой ею секции.
Работа машины Поста.
Работа машины Поста состоит в том, что каретка передвигается вдоль ленты и печатает или стирает метки. Эта работа происходит по инструкции, называемой программой. Для машины Поста возможно составление различных программ. Каждая программа машины Поста состоит из команд. Командой машины Поста называют выражение, имеющее структуру n K m, где n – порядковый номер команды, K – действие, выполняемое кареткой, m – номер следующей команды, подлежащей выполнению.
Существует всего шесть команд машины:
Команда машины Поста | Выполняемое действие |
n ® m | Передвинуть каретку вдоль ленты на одну секцию вправо |
n m | Передвинуть каретку вдоль ленты на одну секцию влево |
n M m | Нанесение метки в секцию, над которой находится головка |
n C m | Стирание метки из секции, над которой находится головка |
Проверка наличия метки в секции, над которой находится каретка. Если метка отсутствует, то управление передается команде m1, иначе m2. | |
n стоп m | Остановка машины |
Ситуации, в которых каретка должна наносить метку там, где она уже имеется, или наоборот, стирать метку там, где ее нет, являются аварийными (недопустимыми).
|
Что бы машина Поста начала работать, надо задать: некоторую программу, некоторое машинное состояние, т.е. расставить метки по секциям и поставить каретку против одной из секций. Как правило, предполагают, что в начальном состоянии машины каретка ставится всегда против секции с номером нуль.
|
|
Своеобразие русской архитектуры: Основной материал – дерево – быстрота постройки, но недолговечность и необходимость деления...
Таксономические единицы (категории) растений: Каждая система классификации состоит из определённых соподчиненных друг другу...
Механическое удерживание земляных масс: Механическое удерживание земляных масс на склоне обеспечивают контрфорсными сооружениями различных конструкций...
Типы сооружений для обработки осадков: Септиками называются сооружения, в которых одновременно происходят осветление сточной жидкости...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!