Остановимся на представлении чисел на ленте машины Поста и выполнении операций над ними

3. Остановимся на представлении чисел на ленте машины Поста и выполнении операций над ними.

Число k представляется на ленте машины Поста идущими подряд k + 1 метками (одна метка означает число «О»). Между двумя числами делается интервал как минимум из одной пустой секции на ленте. Например, запись чисел 3 и 5 на ленте машины Поста будет выглядеть так:

Обратим внимание, что используемая в машине Поста система записи чисел является непозиционной.

Составим программу для прибавления к произвольному числу единицы. Предположим, что на ленте записано только одно число и головка находится над одной из клеток, в которой находится метка, принадлежащая этому числу:

Для решения задачи можно переместить головку влево (или вправо) до первой пустой клетки, а затем нанести метку.

Программа, добавляющая к числу метку слева, имеет вид:

Программа, добавляющая к числу метку справа, имеет вид:

(отличие только в направлении движения головки в первой команде. Проверьте работоспособность этих программ на каких-либо частных примерах).

Предположим, что головка расположена на расстоянии нескольких клеток слева от числа, к которому нужно прибавить единицу. В этом случае программа усложняется. Появится «блок поиска числа» - две команды, приводящие головку в состояние, рассмотренное в предыдущем примере:

Ниже - полные тексты программ, добавляющие единицу слева и справа, соответственно:

В первом случае не нужно перемещать головку к крайней левой метке числа

4. Приведем программу для сложения целых неотрицательных чисел а и и на машине Поста, когда головка находится над числом а, а число b находится правее числа а на некоторое число клеток. Эта программа реализует следующий алгоритм: первое число постепенно придвигается ко второму до их слияния, а потом стирается одна метка (иначе результат оказался бы на единицу больше правильного).

В случае более сложных начальных условий, когда неизвестно, справа или слева от головки (и на какое число клеток) находится число, можно применить такой принцип поиска числа: двигая головку вправо и влево и отмечая метками степень удаления головки от исходного положения, найти число, а потом уже применить известную программу сложения. При этом проверяется, находится ли головка над одной из меток числа и если да, то задача решена. Иначе проверяется, пуста ли секция справа от головки и следующая за ней; если обе пусты, то делается возврат головки на один шаг и ставится метка, а затем такая же операция выполняется слева и по отмеченной дорожке головка возвращается вправо и т.д. до тех пор, пока головка не натолкнется на число, после чего можно применить ранее рассмотренные выше программы:

Машину Поста можно рассматривать как упрощенную модель ЭВМ. В самом деле, как ЭВМ, так и машина Поста имеют:

• неделимые носители информации (клетки - биты), которые могут быть заполненными или незаполненными;

• ограниченный набор элементарных действий - команд, каждая из которых

выполняется за один такт (шаг).

Обе машины работают на основе программы. Однако, в машине Поста информация располагается линейно и читается подряд, а в ЭВМ можно читать информацию по адресу; набор команд ЭВМ значительно шире и выразительнее, чем команды машины Поста и т.д.

 

1.3. МАШИНА ТЬЮРИНГА

Машина Тьюринга подобна машине Поста, но функционирует несколько иначе.

Машина Тьюринга (МТ) состоит из счетной ленты (разделенной на ячейки и ограниченной слева, но не справа), читающей и пишущей головки, лентопротяжного механизма и операционного исполнительного устройства, которое может находиться в одном из дискретных состояний qo, q1,..., qs, принадлежащих некоторой конечной совокупности (алфавиту внутренних состояний). При этом qо называется начальным состоянием.

Читающая и пишущая головка может читать буквы рабочего алфавита А = [а0, a1,..., аt}, стирать их и печатать. Каждая ячейка ленты в каждый момент времени занята буквой из множества А. Чаще всего встречается буква a0 - «пробел». Головка находится в каждый момент времени над некоторой ячейкой ленты - текущей рабочей ячейкой. Лентопротяжный механизм может перемещать ленту так, что головка оказывается над соседней ячейкой ленты. При этом возможна ситуация выхода за левый край ленты (ЛК), которая является аварийной (недопустимой), или машинного останова (МО), когда машина выполняет предписание об остановке.

Порядок работы МТ (с рабочим алфавитом a0, a1,..., аt и состояниями q0, q1,..., qs) описывается таблицей машины Тьюринга. Эта таблица является матрицей с четырьмя столбцами и (s + 1) (t + 1) строками. Каждая строка имеет вид

Здесь через vij обозначен элемент объединения алфавита {а0, а1,..., аt} и множества предписаний для лентопротяжного механизма: l - переместить ленту влево, r - переместить ленту вправо, s - остановить машину; vij - действие МТ, состоящее либо в занесении в ячейку ленты символа алфавита a0, а1,..., аt, либо в движении головки, либо в останове машины; qij является последующим состоянием.

МТ работает согласно следующим правилам: если МТ находится в состоянии qi, головка прочитывает символ 0 в рабочей ячейке. Пусть строка qi аj vij qij, начинающаяся с символов qi, aj, встречается только один раз в таблице. Если vij - буква рабочего алфавита, то головка стирает содержимое рабочей ячейки и заносит туда эту букву. Если vij - команда r или l для лентопротяжного механизма, то лента сдвигается на одну ячейку вправо или влево (если не происходит выход за левый край ленты) соответственно. Если vij =s, то происходит машинный останов.

Машина Тьюринга начинает работу из некоторой начальной конфигурации, включающей в себя начальное состояние (обычно q0) и положение считывающе-записывающей головки над определенной ячейкой ленты, содержащей один из символов рабочего алфавита A.

Отметим, что наличие разнообразных символов в рабочем алфавите МТ позволяет представлять на ленте произвольную текстовую и числовую информацию, а переходы управляющего центра МТ в различные состояния моделируют запоминание машиной Тьюринга промежуточных результатов работы. Таблица, определяющая порядок работы МТ, не является в прямом смысле слова программой (ее предписания выполняются не последовательно, одно за другим, а описывают преобразования символов некоторого текста, находящегося на ленте). Таблицу МТ часто называют схемой машины Тьюринга или попросту отождествляют с самой машиной Тьюринга, коль скоро ее устройство и принцип функционирования известны.

Рассмотрим примеры нескольких схем машины Тьюринга.

1. Алгоритм прибавления единицы к числу п в десятичной системе счисления. Дана десятичная запись числа п (т.е. представление натурального числа п в десятичной системе счисления); требуется получить десятичную запись числа п + 1.

Очевидно, что внешний алфавит МТ должен состоять из десяти цифр 0,1,2,3,4,5,6,7,8,9 и символа пробела _. Эти цифры записывают по одной в ячейке (подряд, без пропусков).

Оказывается достаточным иметь два внутренних состояния машины: q1 и q2.

Предположим, что в начальный момент головка находится над одной из цифр числа, а машина находится в состоянии q1. Тогда задача может быть решена в два этапа: движения головки к цифре единиц числа (во внутреннем состоянии q1) и замене этой цифры на единицу большую (с учетом переноса 1 в следующий разряд, если это 9, во внутреннем состоянии q2. Соответствующая схема МТ может иметь вид

аi	qi
	q1	q2
0	0Пq1	1Cq2
1	1Пq1	2Cq2
2	2Пq1	3Cq2
3	3Пq1	4Cq2
4	4Пq1	5Cq2
5	5Пq1	6Cq2
6	6Пq1	7Cq2
7	7Пq1	8Cq2
8	8Пq1	9Cq2
9	9Пq1	0Cq2
-	-Лq1	1Cq2

2. Алгоритм записи числа в десятичной системе счисления.

Дана конечная последовательность меток, записанных в клетки ленты подряд, без пропусков. Требуется записать в десятичной системе число этих меток пересчитать метки).

Суть алгоритма может состоять в том, что к числу 0, записанному на ленте в начале работы машины, машина добавляет 1, стирая метку за меткой, так что вместо нуля возникает число 0 + k.

Легко могут быть построены алгоритмы сложения чисел, их перемножения, нападения наибольшего общего делителя и т.д. Однако, главная цель введения машин Поста и Тьюринга не программирование для них, а изучение свойств алгоритмов и проблемы алгоритмической разрешимости задач.

В зависимости от числа используемых лент, их назначения и числа состояний устройства управления можно рассматривать различные модификации машин Тьюринга.

Предположим, мы расширили определение МТ, добавив определенное состояние q. устройства управления машины. Будем говорить, что если устройство управления переходит в состояние q0 для заданного входного слова х, то машина допускает х; если устройство переходит в состояние qx, то машина запрещает х. Такую машину будем называть машиной Тьюринга с двумя выходами. Могут быть рассмотрены многочисленные варианты машины Тьюринга, имеющие некоторое конечное число лент. В каждой клетке этих лент может находиться один из символов внешнего алфавита А = {a0, a1,..., аn}. Устройство управления машиной в каждый момент времени находится в одном из конечного множества состояний Q = {q0, q1,..., qm}. Для K-ленточной машины конфигурация ее в i-й момент времени описывается системой k-слов вида:

ail1 … aillqi aill+1 … si1t;

aik1 … aiklqi aikl+1 …aikv;

первый индекс соответствует моменту времени, второй - номеру ленты, третий - номеру клетки, считая слева направо. Говорят, что машина выполняет команду

qiaa1 … aak → qj ab1 k1 … abk kk,

К = {Л, С, П}.

Если, находясь в состоянии qi и обозревая ячейки с символами aa1 - aаk, машина переходит в состояние qj, заменяя содержимое ячеек соответственно символами аb1 - аbк, то после этого ленты соответственно сдвигаются в направлениях k1... kk.

До сих пор принималось, что различные алгоритмы осуществляются на различных машинах Тьюринга, отличающихся набором команд, внутренним и внешним алфавитами. Однако, можно построить универсальную машину Тьюринга, способную выполнять любой алгоритм любой машины Тьюринга. Это достигается путем кодирования конфигурации и программы любой данной машины Тьюринга в символах внешнего алфавита универсальной машины. Само кодирование должно выполняться следующим образом:

1) различные символы должны заменяться различными кодовыми группами, но один и тот же символ должен заменяться всюду, где бы он не встретился, одной и той же кодовой группой;

2) строки кодовых записей должны однозначно разбиваться на отдельные кодовые группы;

3) должна иметься возможность распознать кодовые группы, соответствующие командам Л, П, С, различать кодовые группы, соответствующие символам внешнего алфавита и внутренним состояниям.

Для сравнения структур различных машин и оценки их сложности необходимо иметь соответствующую меру сложности машин.К. Шеннон предложил рассматривать в качестве такой меры произведение числа символов внешнего алфавита и числа внутренних состояний. Большой интерес вызывает задача построения универсальной машин Тьюринга наименьшей сложности.

Может быть рассмотрено еще одно обобщение машин Тьюринга: их композиции. Операции композиции, выполняемые над алгоритмами, позволяют образовывать новые, более сложные алгоритмы из ранее известных простых алгоритмов. Поскольку машина Тьюринга - алгоритм, то операции композиции применимы и к машинам Тьюринга. Рассмотрим основные из них: произведение, возведение в степень, итерацию.

Пусть заданы машины Тьюринга T1 и T2, имеющие общий внешний алфавит А = {a0, a1,..., am} и внутренние состояния Q1 = {q0, q1,… qn} и Q2 = {q0, q1,..., qt} соответственно. Композицией или произведением машины T1 и машины T2 будем называть машину Т с тем же внешним алфавитом А = {a0, а1,..., am} и набором внутренних состояний Q = {q0, q1,..., q2,, qn+1,..., qn+1} и программой, эквивалентной последовательному выполнению программ машин Т1 и Т2:

Т = T1 * T2. .

Таким же образом определяется операция возведения в степень: n-й степенью машины Т называется произведение T... Т c n сомножителями.

Операция итерации применима к одной машине и определяется следующим образом. Пусть машина T1 имеет несколько заключительных состояний. Выберем ее r-е заключительное состояние и отождествим его в схеме машины с ее начальным состоянием. Полученная машина T является результатом итерации машины Т1: Т = T1.

Прежде чем остановиться на проблеме алгоритмической разрешимости задач обратимся к другим способам формализации понятия алгоритма.