Таксономические единицы (категории) растений: Каждая система классификации состоит из определённых соподчиненных друг другу...
Индивидуальные очистные сооружения: К классу индивидуальных очистных сооружений относят сооружения, пропускная способность которых...
Топ:
Техника безопасности при работе на пароконвектомате: К обслуживанию пароконвектомата допускаются лица, прошедшие технический минимум по эксплуатации оборудования...
Генеалогическое древо Султанов Османской империи: Османские правители, вначале, будучи еще бейлербеями Анатолии, женились на дочерях византийских императоров...
Процедура выполнения команд. Рабочий цикл процессора: Функционирование процессора в основном состоит из повторяющихся рабочих циклов, каждый из которых соответствует...
Интересное:
Берегоукрепление оползневых склонов: На прибрежных склонах основной причиной развития оползневых процессов является подмыв водами рек естественных склонов...
Наиболее распространенные виды рака: Раковая опухоль — это самостоятельное новообразование, которое может возникнуть и от повышенного давления...
Отражение на счетах бухгалтерского учета процесса приобретения: Процесс заготовления представляет систему экономических событий, включающих приобретение организацией у поставщиков сырья...
Дисциплины:
2019-11-19 | 147 |
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 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!