Композиция машин тьюринга примеры. Графическое представление

Цель работы: получить практические навыки в записи алгоритмов с использованием композиции машин Тьюринга.

Теоретическая справка

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

Опишем 4 основных способа композиции МТ:

Последовательная композиция (суперпозиция);

Параллельная композиция;

Разветвление

1. Последовательная композиция машин Тьюринга

Последовательной композицией или суперпозицией машин Тьюринга и

и
в алфавите А, называется машина M , вычисляющая функцию
.

Последовательная композиция изображается следующим образом:

и обозначается
или
.

2. Параллельная композиция машин Тьюринга

Параллельной композицией машин
и
, вычисляющих словарные функции
и
в алфавитах А и В, соответственно, называется машина M , вычисляющая словарную функцию . Здесь знак используется для разделения слов при параллельной композиции МТ.

Параллельная композиция МТ
и
изображается следующим образом:

и обозначается:
.

Фактически параллельная композиция двух МТ получает на вход слово, состоящее из 2-х слов в разных алфавитах, и на выходе выдает слово, также состоящее из 2-х слов, т.е. представляет собой две одновременно и независимо работающие машины. Для реализации параллельной композиции используется машина с двухэтажной лентой.

Машина с двухэтажной лентой работает следующим образом:

1) слово переписывается на второй этаж ленты и стирается на первом,

2) вычисляется
на первом этаже,

3) вычисляется
на втором этаже

4)
переписывается на первый этаж, возможно, со сдвигом.

Команда МТ с двухэтажной лентой записывается следующим образом:

,

где
– буквы, записанные соответственно на первом и втором этажах. Обозначим длины слов
, соответственно,
.

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

Для реализации параллельной композиции n машин Тьюринга используется n – этажная лента.

3. Разветвление или условный переход в композиции машин Тьюринга

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

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

и обозначается
, здесь
– результат работы машины
, принимающий значения «1», если предикатP ( )= ”true ” и «0», если предикат P ( )= “false ” ,
– машина Тьюринга, реализуюшая копирование входного слова
.

4 . Цикл в композиции машин Тьюринга

Цикл в композиции МТ реализуется по тем же принципам, что и разветвление.

« пока P( )= ”true ” , выполнять
»,

где  – слово на ленте перед первым выполнением
ипосле очередного выполнения.

Для изображения цикла введем некоторые обозначения, пусть:

–машина Тьюринга, реализующая вычисление предиката P( ) ;

–МТ, реализующая копирование входного слова
;

–МТ, выполняемая в цикле и реализующая
;

–МТ, выполняемая при выходе из цикла и реализующая
.

Тогда, циклическая композиция машин Тьюринга или цикл, может быть изображена следующим образом:

Программирование с помощью композиций машин Тьюринга:

1) построение блок-схем сложных алгоритмов такой степени детализации, что их блоки соответствуют элементарным МТ;

2) построение элементарных МТ, реализующих простые блоки;

3) объединение элементарных МТ в композицию МТ.

Пример. Построить композицию МТ, реализующую
.

–машина Тьюринга, реализующая копирование входного слова;

–МТ, реализующая функцию установки константы ноль;

–МТ, вычисляющая предикат с восстановлением
;

– МТ, реализующая функцию выбора-того аргумента изаргументов;

–МТ, реализующая функцию уменьшение аргумента на 1 в унарном коде (вытирает крайний левый символ);

– МТ, выполняющая сложение двух чисел в унарном коде.

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

Определение, функционирование и способы задания машины Тьюринга

Под машиной Тьюринга понимается некоторая гипотетическая (абстрактная) машина, состоящая из следующих частей (рис. 3.1.)

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

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

Рис. 3.1. Машина Тьюринга

Функционирование МТ состоит из последовательности элементарных шагов (тактов). В каждом шаге выполняются следующие действия:

1. рабочая головка считывает (обозревает) символ ;

2. в зависимости от своего состояния и обозреваемого символа головка вырабатывает символ и записывает его в обозреваемую ячейку (возможно =) ;

3. головка перемещается на одну ячейку вправо (R) , влево (L) или остается на месте (E) ;

4. головка переходит в другое внутреннее состояние . (возможно =).

Состояние называется начальным, - заключительным. При переходе в заключительное состояние машина останавливается.

Полное состояние МТ называется конфигурацией . Это распределение букв по ячейкам ленты, состояние рабочей головки и обозреваемая ячейка. Конфигурация в такте t записывается в виде: , где - подслово слева от обозреваемой ячейки, - буква в обозреваемой ячейке, - подслово справа.

Начальная конфигурация и конечная называются стандартными.

Для описания работы МТ существует 3 способа:

Система команд вида

Функциональная таблица;

Граф (диаграмма) переходов.

Рассмотрим их на примерах.

Пример 1. Построить МТ, реализующую конкатенацию двух слов в алфавите . Слова на ленте разделены знаком * . Начальная конфигурация является стандартной.

Система команд МТ имеет вид:

В состоянии осуществляется движение головки вправо до пустого символа.

Самый правый символ стирается.

Звездочка стирается, если первое слово пустое.

Правое слово посимвольно сдвигается влево на одну позицию.

Переход в стандартную конечную конфигурацию.

Функциональная таблица

Прочерки в таблице означают, что символ l не может быть встречен в состояниях .

Стандартная заключительная конфигурация.

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

С помощью МТ можно описывать выполнение арифметических операций над числами. При этом числа представляются на ленте как слова в алфавите, состоящем из цифр какой-нибудь системы счисления, и разделяющихся специальным знаком, не входящем данный алфавит, например, * . Наиболее употребительной системой является унарная, состоящего из одного символа –1. Число Х на ленте записывается словом , (или сокращенно ) в алфавите А={1} .

Числовая функция правильно вычислима (или просто вычислима) по Тьюрингу, если существует МТ, которая переводит конфигурацию в конфигурацию , когда =y , или работает бесконечно, когда не определена.

Пример 2. Операция сложения двух чисел в унарном коде.

Начальная конфигурация:

Конечная конфигурация: т.е. сложение фактически сводится к приписыванию числа b к числу a . Для этого первая 1 стирается, а * заменяется на 1.

Приведем описание МТ в виде функциональной таблицы:

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

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

Опишем 4 основных способа композиции МТ:

Последовательная композиция (суперпозиция);

Параллельная композиция;

Разветвление

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

и обозначается .

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

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

Пример 3. Построить алгоритм умножения 2*Х в унарном коде с использованием машины копирования , переводящей слово a в слово a*a и машины сложения . Искомая МТ выглядит следующим образом:

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

и обозначается: .

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

Для реализации параллельной композиции используется машина с двухэтажной лентой. Необходимость в этом вызвана тем, что вычисление и во времени происходит последовательно, и , вычисленная, например, первой, может потребовать больше места, чем a, и испортить слово b. Машина с двухэтажной лентой работает следующим образом: слово b переписывается на второй этаж и стирается на первом, вычисляется на первом этаже, вычисляется на втором этаже и затем переписывается на первый этаж, возможно, со сдвигом.

Для реализации параллельной композиции n машин используется n– этажная лента.

Команда МТ с двухэтажной лентой записывается следующим образом:, где - буквы, записанные соответственно на первом и втором этажах.

Пример 4 . Реализовать параллельную композицию машин и , вычисляющих функции в двоичной системе счисления и a + b в унарной системе.

Входное слово имеет вид: .

Опишем работу МТ системой команд:

Движение вправо до слова b

Перезапись слова b на второй этаж

Движение влево до слова a

Прибавление 1 к числу Х.

Движение вправо к слову b.

Перепись b на 1-й этаж с одновременным сложением чисел a и b .Т соответственно. Команды в фигурных скобках, добавленные к системе команд

Конечное состояние всей МТ.

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

Композиция МТ может применяться для построения сложных алгоритмов. Возникает вопрос: всякий ли алгоритм можно реализовать в виде композиции МТ? Ответ на этот вопрос дает Тезис Тьюринга , аналог тезиса Черча: всякий алгоритм может быть реализован с помощью машин Тьюринга и наоборот, всякий процесс, реализуемый машиной Тьюринга, является алгоритмом.

Тезис Тьюринга не является теоремой, доказать его невозможно, т.к. он содержит неформальное понятие « алгоритм ». Однако многолетняя математическая практика является надежным подтверждением этого тезиса: за 50 лет не было найдено алгоритма в интуитивном смысле, который нельзя было бы реализовать с помощью машин Тьюринга.

Функционирование машины Тьюринга:

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

Машина Тьюринга работает с тремя алфавитами:

1. входной алфавит А ={а 0 …а n }, с помощью которого записывается входная, промежуточная, выходная информация. а 0 – пустой символ (незначащий ноль, Ù, В , #), а 1 – 1 или |

2. внутренний алфавит, или алфавит состояний Q ={q 0 …q m }, q 0 - заключительное состояние q 1 – начальное состояние q 0 …q n – рабочее состояние

3. алфавит сдвига {Л, В, Н} или {-1, +1, 0} (влево, вправо, на месте)

Машина Тьюринга состоит из следующих частей:

1) лента , потенциально бесконечная в обе стороны. Потенциальная бесконечность означает, что в каждый момент времени на ленте записано конечное слово, но в случае необходимости слева и справа от слова можно достроить необходимое количество ячеек. Лента разделена на ячейки, в каждой из которых записан только один символ входного алфавита. В пустых ячейках записан пустой символ. Если в ячейке информацию необходимо стереть, то достаточно записать в неё пустой символ.

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

3) головка (считывающее и записывающее устройство) в каждый момент времени выполняет следующие действия

· считывает символ, записанный в ячейке

· заменяет его на другой символ алфавита А или оставляет прежним

· сдвигается по ленте вправо, влево на одну ячейку или остается на месте

Правило работы машины Тьюринга:

Машина Тьюринга, находясь в состоянии q i и считывая символ a j , записывает в данную ячейку символ а k , переходит в состояние q e , осуществляет сдвиг. При этом говорят, что машина выполнила одну команду: a j q i ®a k q e S SÎ{Л, П, Н}

Совокупность команд называется программой МТ.

a j q i – исходные символы команд должны быть различны. Если это условие выполняется, машина называется детерминированной , в противном случае – недетерминированной . Машина работает в дискретные моменты времени.

Таким образом, полное описание машины Тьюринга в каждый момент времени, по которому можно определить её дальнейшее поведение, содержит инфу о:

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

Работа машины Тьюринга может быть представлена как последовательность конфигураций k 1 ®k 2 ®…®k n .

Стандартная начальная конфигурация – считывание крайнего левого непустого символа в состояние q 1

Стандартная заключительная конфигурация – машина перешла в заключительное состояние:

Если машина перешла в заключительное состояние, она применима к данному входному слову, если работает бесконечно, значит, машина не применима к данному слову.

МТ представляет собой совокупность, состоящую из входного алфавита, алфавита состояний и программы. M = . А – входной алфавит Q – внутренний алфавит П – программа

Программа машины может быть задана следующим образом:

1) списком команд: a j q i ®a k q n S

2) с помощью таблицы

3) с помощью графа предикатов (вершины – состояния, каждой команде соответствует дуга)

Конструирование машин Тьюринга:

Сконструировать машину Тьюринга – построить её программу. Проходит в два этапа:

1) словесное описание алгоритма решаемой задачи

2) перевод словесного описания алгоритма на язык машины Тьюринга (для этого задаются A , Q , П )

Пример : построить машину Тьюринга, которая вычисляет функцию f(n)=n+1, где n задано в двоичной системе исчисления.

А ={0,1,a 0 }, множество Q определяется в процессе построения программы.

Алгоритм:

1. перевести головку из крайнего правого состояния в крайнее левое

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

Повторить Шаг 2

Пример : На ленте записано натуральное десятичное число. Необходимо сконструировать машину Тьюринга, увеличивающую это число на 1. Изначально головка указывает на первую цифру числа. Получаем: A = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, a 0 }, Q = {q 1 , q 2 , q 0 }. П – см. таблицу.

Общая идея – переместить головку на последнюю цифру числа, и если эта цифра не 9, то увеличить её на единицу, иначе обратить в ноль и перейти к предыдущей ячейке.

Композиция машин:

Композиция машин представляет собой последовательное выполнение двух машин.

Т 1 =(A 1 , Q 1 , П 1 ) Т 2 =(A 2 , Q 2 , П 2 ) Q 1 Ç Q 2 =Æ

Композицией машин Т 1 °Т 2 называется машина Т (A , Q , П ), где А =А 1 ÈA 2 ; Q =(Q 1 ÈQ 2 )\{q 10 } (q 10 – заключительное состояние Т 1 ). Машина Т работает по следующему правилу: U – некоторое слово, Т (U )=Т 1 °Т 2 (U )=Т 2 (Т 1 (U ))

Теорема. Композиция машин Т 1 °Т 2 существует.

Q 1 ={q 10 , q 1 ,…, q n }

Q 2 ={q 20 , q` 1 , …, q` n }, тогда для построения Q удалим состояние q 10 , переобозначив его в q n +1 , которое совпадает с начальным состоянием второй машины, а все остальные состояния - в q` i =q n + 1 .

Вычислимые по Тьюрингу функции:

Функция f(x 1 …x n) называется вычислимой по Тьюрингу , если существует машина Тьюринга, вычисляющая значение этой функции, когда заданы значения аргументов. Функция f(x 1 …x n) задана на множестве натуральных чисел, но теория алгоритмов рассматривает расширенное множество натуральных чисел NÈ{0}.

Аргументы функции f(x 1 …x n) на ленте представляются в виде следующего слова:

Каждому аргументу соответствует столько палочек, каково значение этого аргумента. Если функция f определена на данном наборе значений переменной x 1 …x n , то в результате работы машины Тьюринга на ленте должно остаться такое количество палочек, записанных подряд, которое равно значению функции на данном наборе. Если функция f не определена на данном наборе, то машина Тьюринга должна работать бесконечно.

Начальная конфигурация – считывание крайней левой палочки.

Диаграмма имеет вид графа:

Табличное значение машины

Таблица 1

1. Некоторые операции над машинами Тьюринга

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

Теорема 1 . Если
и
вычислимы по Тьюрингу, то их композиция
также вычислима по Тьюрингу.

Пусть - машина, вычисляющая, а- машина, вычисляющая, и множество их состояний соответственно
и
.

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

Пусть
определена. Тогда
и

. Машинапройдет ту же последовательность конфигураций с той разницей, что вместо
она пройдет в
. Эта конфигурация является стандартной начальной конфигурацией для машины, поэтому
. Но так как все командысодержатся в, то

и, следовательно,
. Если же
не определена, тоилине останавливается и, следовательно, машинане остановится. Итак, машинавычисляет
.

Построенную таким образом машину будем называть композицией машинии обозначать
(или()), а также изображать блок-схемой:

1. Композиция машин Тьюринга

Пусть ,,- три машины Тьюринга с одним и тем же внешним алфавитом
, с алфавитами внутренних состояний
,
,
и программами,
,
соответственно.

Композицией
машининазываетсямашина Т , программа которой есть объединение множеств
и

, где
обозначает множество команд, полученных иззаменой всехна.

1. Разветвление машин Тьюринга

Разветвлением машин ,,по
, символически

называетсямашина T , программа которой получается следующим образом: изисключаются команды
и
для
, полученное множество назовем; тогда.

1. Универсальная машина Тьюринга

Систему команд машины Тьюринга можно интерпретировать и как описание работы конкретного устройства и как программу, т.е. совокупность предписаний, однозначно приводящих к результату. При разборе примеров невольно принимается вторая интерпретация, т.е. мы выступаем в роли механизма, который способен воспроизвести работу любой машины Тьюринга. Уверенность в том, что все это будут делать одинаково (если не наделают ошибок, что, кстати, предполагается и при работе машины Тьюринга) - это по существу уверенность в существовании алгоритма воспроизведения работы машины Тьюринга по заданной программе, т.е. системе команд. Действительно, словесное описание такого алгоритма дать нетрудно. Его основное действие циклически повторяется и состоит в следующем: "Для текущей конфигурации
найти в системе команд команду с левой частью
. Если правая часть этой команды имеет вид
, то заменить в текущей конфигурации
на
(получается конфигурация
); если же правая часть имеет вид
, то заменить
на
. Словесное описание алгоритма может быть неточным и нуждается в формализации. Поскольку в качестве такой формализации понятия алгоритма сейчас обсуждается машина Тьюринга, то естественно поставить задачу построения машины Тьюринга, реализующей описанный алгоритм воспроизведения. Для машин Тьюринга, вычисляющих функции от одной переменной, формулировка этой задачи такова: построить машину Тьюринга, вычисляющую функцию от двух переменных и такую, что для любой машиныс системой команд
, если
определена (т.е. если машинаостанавливается при исходных данных) и
не останавливается, если
не останавливается. Любую машину, обладающую указанным свойством, будем называтьуниверсальной машиной Тьюринга . Нетрудно обобщить эту формулировку на любое число переменных.

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

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


, если

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

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

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

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

В предыдущем параграфе мы рассмотрели, каким образом «данная машина Тьюринга вычисляет функцию f (, …,)». Для этого нужно, чтобы каждое из чисел, …, было записано на ленту машины непрерывным массивом из соответствующего числа единиц, а сами массивы были разделены символом 0. Если функция f (, …, определена на данном наборе значений аргументов, то в результате на ленте должно быть записано подряд f (, …,) единиц. При этом мы не очень строго относились к тому, в каком начальном положении машина начинает работать (часто это было стандартное начальное положение), в каком завершает работу и как эта работа протекает.

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

Определение 5.1: Будем говорить, что машина Тьюринга правильно вычисляет функцию f (, …,), если начальное слово 0…0 она переводит в слово 0…0 и при этом в процессе работы не пристраивает к начальному слову новых ячеек на ленте ни слева, ни справа. Если же функция f не определена на данном наборе значений аргументов, то, начав работать из указанного положения, она никогда в процессе работы не будет надстраивать ленту слева.

Пример 5.1. Приведем программы машин Тьюринга, правильно вычисляющих функции S(x) = x+1 и O(x) = 0. Функция S(x) = x+1 осуществляет перевод: 0 => . Ее программа: 0 > П, 1 > 1П, 0 > 1, 1 > 1Л, 0 > 0. Функция O(x) = 0 осуществляет перевод: 0 => . Ее программа: 0 > 0П, 1 > 1П, 0 > 0Л, 1 > 0, 0 > 0Л, 0 > 0. Соответствующую машину Тьюринга обозначили О.

Пример 5.2. Построить две машины «левый сдвиг» и «правый сдвиг» . Первая из начального стандартного положения перерабатывает слово 0 в то же самое слово и останавливается, обозревая самую левую ячейку с нулем. Вторая машина из начального состояния, в котором обозревается левая ячейка с нулем, слово 0 перерабатывает в то же самое слово и останавливается, обозревая самую правую ячейку с нулем.

Программа машины: 0 > 0Л, 1 > 1Л, 0 > 0. Ясно, что программа машины получается из программы предыдущей машины заменой символа «Л» символом «П».

Композиция машин Тьюринга

Определение 6.1: Пусть заданы машины Тьюринга и, имеющие общий внешний алфавит {, …,} и алфавиты внутренних состояний {, …,} и {, …, } соответственно. Композицией (или произведением) машины на машину называется новая машина с тем же внешним алфавитом {, …,}, внутренним алфавитом {, …, …, } и программой, получающейся следующим образом. Во всех командах из, содержащих символ остановки, заменяем последний на. Все остальные символы в командах из остаются неизменными. В командах из символ остается неизменным, а все остальные состояния (i = 1, …, t) заменяем соответственно на. Совокупность всех так полученных команд образует программу машины-композиции.

Введенное понятие является удобным инструментом для конструирования машин Тьюринга. Покажем это на примере.

Пример 6.1. Сконструируем машины Тьюринга, правильно вычисляющие функции-проекторы (, …,) = (1? m ? n).

Рассмотрим сначала конкретный случай n=3, m=2, т.е. функцию (,) = . Мы должны переработать слово 0 в слово 0. Будем применять к начальной конфигурации последовательно сконструированные ранее машины Тьюринга, В, О:

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

Теперь мы можем представить себе алгоритм построения композиции машин, В, О для вычисления любой функции вида (, …,) = . С помощью правого сдвига, применив его m-1 раз, нужно сначала достичь массива:

Затем, двигаясь влево, транспонировать (с помощью В) массив с каждым соседним слева массивом, пока массив не выйдет на первое место:

Теперь нужно дойти до крайнего правого массива с помощью (n-1) - кратного применения правого сдвига:

Наконец, нужно стирать последовательно справа налево все массивы единиц, кроме первого:

Итак, данную функцию (правильно) вычисляет следующая машина Тьюринга.