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

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

сложной, нежели процесс применения данной машины к данным словам.

Пример 3. Попытаемся построить такую машину Тьюринга, которая из пзаписанных подряд единиц оставляла бы на ленте n-2 единицы, также записанные подряд, если п > 2, и работала бы вечно, если п = 0 или п = 1.

В качестве внешнего алфавита возьмем двухэлементное множество А = {0,1}. Количество необходимых внутренних состояний будет определено в процессе составления программы. Считаем, что машина начинает работать из стандартного начального положения, т.е. когда в состоянии q₁ обозревается крайняя правая единица из п записанных на ленте.

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

q₁1→ q₂0Л; q₂1→ q₃0Л.

Машина находится в состоянии q₃ обозревает третью справа ячейку из тех, в которых записано данное слово (п единиц). Не меняя содержимого обозреваемой ячейки, машина должна остановиться, т.е. перейти в заключительное состояние q₀, независимо от содержимого ячейки. Вот эти команды:

q₃0→ q₀0; q₃1→ q₀1.

Теперь остается рассмотреть ситуации, когда на ленте записана всего одна единица или не записано ни одной. Если на ленте записана одна единица, то после первого шага (выполнив команду q₁1→ q₂0Л) машина будет находиться в состоянии q₂ и будет обозревать вторую справа ячейку, в которой записан 0. По условию, в таком случае машина должна работать вечно. Это можно обеспечить, например, такой командой:

q₂0→ q₂0П,

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

q₁0→ q₁0П.

Запишем составленную программу (функциональную схему)

построенной машины Тьюринга в виде таблицы:

A\Q	q1	q2	q3
0	q10П	q20П	q00
1	q10Л	q20Л	q01

В заключение отметим следующее. Созданная нами машина Тьюринга может применяться не только к словам в алфавите А = {0, 1}, представляющим собой записанные подряд п единиц (п > 2). Она применима и ко многим другим словам в этом алфавите, например, к словам: 1011, 10011, 111011, 11011, 1100111, 1001111, 10111, 10110111, 10010111 и т.д. (исходя из стандартного начального положения). С другой стороны, построенная машина не применима (т. е. при подаче этих слов на вход машины она работает вечно) не только к слову «1» или к слову, состоящему из одних нулей. Она не применима и к следующим словам (проверьте самостоятельно): 101, 1001, 11101, 101101, 1100101101 и т.д.

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

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

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

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

Во-вторых, нужно условиться, как записывать на ленте машины Тьюринга значения п аргументов функции f(x₁, x₂, ..., х_п), из какого положения начинать переработку исходного слова и, наконец, в каком положении получать значение функции. Это можно делать, например, следующим образом. Значения п аргументов будем располагать на ленте в виде следующего слова:

Здесь полезно ввести следующие обозначения. Для натурального х обозначаем:

; .

так, что на слова: - пустое слово; …будем смотреть как на «изображения» натуральных чисел 0, 1, 2, 3, ... соответственно.

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

образом:

Далее, начинать переработку данного слова будем из стандартного начального положения, т.е. из положения, при котором в состоянии q₁ обозревается крайняя правая единица записанного слова. Если функция f(x₁, x₂, ..., х_п) определена на данном наборе значений аргументов, то в результате на ленте должно быть записано подряд f(x₁, x₂, ..., х_п) единиц; в противном случае машина должна

работать бесконечно.

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

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

Пример. Построим машину Тьюринга, вычисляющую функцию f(x)= х/2. Эта функция не всюду определена: областью ее определения является лишь множество всех четных чисел. Поэтому, учитывая определение 1для вычислимой функции, нужно сконструировать такую машину Тьюринга, которая при подаче на ее вход четного числа давала бы на выходе половину этого числа, а при подаче нечетного — работала бы неограниченно долго.

Сконструировать машину Тьюринга — значит написать (составить) еепрограмму. В этом процессе два этапа: сначала создается алгоритм вычисления значений функции, а затем он записывается на языке машины Тьюринга (программируется).

В качестве внешнего алфавита возьмем двухэлементное множество А = {0, 1}. В этом алфавите натуральное число х изображается словом 11... 1, состоящим из х единиц, которое на ленте машины Тьюринга записывается в виде х единиц, стоящих в ячейках подряд.

Работа машины начинается из стандартного начального положения:

01 … 1q₁10 (число единиц равно х).

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

(1): q₁1→ q₂1Л;

(2): q₂1→ q₁0Л ;

(3): q₂0→ q₂0Л.

Если число х единиц нечетно, то машина продолжит движение по ленте влево неограниченно, т. е. будет работать бесконечно. Если же число х единиц четно, то в результате выполнения команд создается конфигурация q₁0010101... 01010, в которой число единиц равно х/2.

Остается сдвинуть единицы так, чтобы между ними не стояли нули. Для

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

(4): q₁0→ q₃0П;

(5): q₃0→ q₃0П;

(6): q₃1→ q₄1П.

В результате их выполнения получим конфигурацию

001q₄ 010101 ... 010100. (*)

Заменим 0, перед которым остановились, на 1 и продвинемся вправо до

ближайшего 0:

(7): q₄0→ q₅1П;

(8): q₅1→ q₂1П.

Получим конфигурацию 00111q₅0101... 010100, в которой правее обозреваемой ячейки записаны «пары» 01, ..., 01. Кроме того, на ленте одна единица записана лишняя. Продвинемся по ленте вправо до последней «пары» 01. Это можно сделать с помощью своеобразного цикла:

(9): q₅0→ q₆0П;

(10): q₆1→ q₂1П.

Получим конфигурацию 001110101 ...01010q₆00.

Двигаться дальше вправо бессмысленно. Вернемся на две ячейки назад и заменим единицу из последней «пары» 01 на ноль:

(11): q₆0→ q₇0Л;

(12): q₇0→ q₇0Л;

(13): q₇1→ q₈0Л.

Получим конфигурацию 001110101 ...01q₈00. Число единиц на ленте снова равно x/2. Продвинемся влево на одну ячейку с помощью команды

(14): q₈0→ q₉0Л.

В результате чего получим конфигурацию 001110101 ...010q₉100. Теперь

уничтожим самую правую единицу и продвинемся по ленте влево до следующей единицы:

(15): q₉1→ q₁₀0Л;

(16): q₁₀0→ q₁₀0Л.

Получим конфигурацию

001110101 ... 0q₁₀100, (**)

в которой левее обозреваемой ячейки записана серия пар 10, 10,…,10 (если читать справа налево). Теперь на ленте недостает одной единицы, т. е. число единиц равно (х/2) - 1. Продвинемся по ленте влево до последней «пары» 10.

Это можно сделать с помощью цикла

(17): q₁₀1→ q₁₁1Л;

(18): q₁₁0→ q₁₀0Л,

выполнив который, придем к следующей конфигурации: 001q₁₁110101...0100. Вернемся вправо к ближайшему нулю и превратим его в

единицу

(19): q₁₁1→ q₁₂1П;

(20): q₁₂1→ q₁₂1П;

(21): q₁₂0→ q₁₃1П.

Получим конфигурацию 001111q₁₃101 ... 0100, в которой число единиц снова равно х/2.

Если теперь перешагнем вправо по ленте через обозреваемую единицу и переведем машину в состояние q₄ с помощью команды

(22): q₁₃1→ q₄1П,

то придем к следующей конфигурации: 0011111q₄01 ... 0100, которая по существу аналогична конфигурации (*). В результате программа зацикливается (становится циклической): снова ближайший 0 превращается в 1, а самая правая 1 — в 0, затем машина возвращается к самому левому нулю, оказываясь в начале следующего цикла, и т.д.

Как же завершается работа программы? В некоторый момент

конфигурация будет иметь вид 00111... 10q₁₀100. Выполнив команды (17), (18),

придем к конфигурации 00111... 1q₁₁ 110100. Далее выполняются команды (19),

(20), (21), что приводит к конфигурации: 00111... 111111q₁₃00. Остается

остановить машину. Это делается с помощью команды

(23): q₁₃0→ q₀0Л.

Заключительная конфигурация имеет вид: 00111... 1111q₀100.

Запишем программу машины Тьюринга в табличной форме: