Тьюрингово вычисления: Алгоритм операции сложения двух целых натуральных чисел.

Исходные данные и результаты операции являются натуральными числами.

Считаем, что в МТ каждое число задано в виде набора «1» и отделяются друг от друга символом «*». Тогда имеем алфавит S = {1, *, ë}. Состояния заданы множеством Q = {q₀, q₁, q₂, q₃, q₄}.

Рассмотрим пример сложения двух чисел: 2+2=4. Начальные условия: На ленту записаны пары чисел, разделенные знаком «*», начальное состояние q0 и обозревается крайняя левая единица.

Изобразим начальные установки и информацию на ленте перед началом работы.

Просто убрать «*» нельзя, т.к. на ее месте будет записан пустой символ (пробел или ë), а совокупность единиц с пробелом не является заданием числа натурального ряда.

Для реализации операции сложения используем таблицу функционирования МТ, записанную в сокращенном виде, т.е. опускаем не изменяемые состояния и символы.

Знак «!» означает остановку работы машины Тьюринга.

Рассмотрим работу примера в соответствии с таблицей функционирования и начальными условиями.

Такт работы МТ	Система команд	Информация на ленте
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	Остановка машины

Ситуации, в которых каретка должна наносить метку там, где она уже имеется, или наоборот, стирать метку там, где ее нет, являются аварийными (недопустимыми).

Что бы машина Поста начала работать, надо задать: некоторую программу, некоторое машинное состояние, т.е. расставить метки по секциям и поставить каретку против одной из секций. Как правило, предполагают, что в начальном состоянии машины каретка ставится всегда против секции с номером нуль.