Cвойства машин Тьюринга.

ОГЛАВЛЕНИЕ

 

 

ОГЛАВЛЕНИЕ.. 2

1. Cвойства машин Тьюринга. 3

2. Операции над машинами Тьюринга. 8

3. Вычислимые функции. 9

4. Варианты заданий.. 13

СПИСОК ЛИТЕРАТУРЫ... 33

 

Cвойства машин Тьюринга.

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

Лента разбита на ячейки (клетки). Во всякой ячейке в каждый дискретный момент времени находится в точности один символ из внешнего алфавита (п ≥ 2). Алфавит А со­держит символ, называемый пустым, а любая ячейка, содержащая в данный момент пустой символ, называется пустой ячейкой (в этот момент). В качестве пустого символа обычно используют 0 (нуль). Лента предполагается потенциально неограниченной в обе стороны. Это следует понимать так: в каждый момент времени лента конечна (т.е. содержит конечное число ячеек), но «размеры» ленты (число ячеек на ней) при необходимости можно увеличивать.

Управляющее устройство в каждый момент времени находится в некотором состоянии q_i, принадлежащем множеству (г ≥ 1). Множество Q называется внутренним алфавитом (или множеством внутренних состояний). Иногда из Q выделяются непересекающиеся подмножества Q₁ и Q₀ начальных и заключи­тельных состояний соответственно.

Замечание: В дальнейшем, если не оговаривается противное, считаем, что , и в качестве начального берем только одно состояние q_i. Заключительным, как правило, будет состояние q₀.

Считывающая (и печатающая) головка перемещается вдоль лен­ты так, что в каждый момент времени она обозревает ровно одну ячейку ленты. Головка считывает содержимое обозреваемой ячейки и записывает в нее (печатает в ней) вместо обозреваемого символа некоторый символ из внешнего алфавита. «Засылаемый» в ячейку символ может, в частности, совпадать с тем, который обозревался (в данный момент).

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

Работа управляющего устройства характеризуется тремя функ­циями:

Функция G называется функцией переходов, функция F — функ­цией выходов и D — функцией движения (головки). Символы S, L и R обозначают соответственно отсутствие движения головки, сдвиг головки на одну ячейку влево и сдвиг на ячейку вправо.

Функции G, F и D можно задать списком пятерок вида

(1)

или, короче, . Эти пятерки называются командами. Функ­ции G, F и D являются, вообще говоря, частичными (не всюду опре­деленными). Это значит, что не для всякой пары определена соответствующая пятерка вида (1). Список всех пятерок, определяю­щих работу машины Тьюринга, называется программой этой машины. Программу машины можно задавать в виде таблицы (табл. 1).

Таблица 1

	. . .   ......   . . .

Если в программе машины для па­ры пятерка вида (1) отсутству­ет, то в таблице на пересечении стро­ки и столбца ставится прочерк.

Работу машины Тьюринга описы­вают также на «языке конфигураций».

Пусть в момент времени t самая левая непустая ячейка C₁ ленты со­держит символ , а самая правая непустая ячейка C_s - символ (между ячейками C₁ и C_s находится ячеек). В этом случае говорят, что в момент t на ленте записано слово , где - cимвол, содержащийся в момент t в ячейке С_р (). При s = 1, т.е. когда на ленте только один непустой символ, . Пусть в этот момент времени управляю­щее устройство находится в состоянии q_i, и головка обозревает сим­вол слова Р . Тогда слово

(2)

называется конфигурацией машины (в данный момент t). При l = 1 конфигурация имеет вид . Если в момент t головка обозревает пустую ячейку, находящуюся слева (справа) от слова Р, и между этой ячейкой и первой (соответственно последней) ячейкой слова Р расположено пустых ячеек, то конфигурацией машины в момент t называется слово

(3)

(соответственно слово ), где через 𝞚 обозначен пустой символ алфавита A. Если в момент t лента пуста, т. е. на ней записано пустое слово, состоящее только из пустых символов внешнего алфавита, то конфигурацией машины в момент t будет слово .

Пусть в момент t конфигурация машины имеет вид (2) и в прог­рамме машины содержится команда

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

а)

б)

в)

Случаи, когда или , или когда либо конфигура­ция машины соответствует головке, находящейся вне слова Р (как в словах (3) и (3')), либо слово Р пустое, описываются аналогично.

Если в программе машины нет пятерки вида (1) для пары или «новое» состояние является заключительным, то машина прекращает работу, а «результирующая» конфигурация называется заключительной. Конфигурация, соответствующая началу работы машины, называется начальной.

Пусть в некоторый момент времени конфигурация машины бы­ла К, а в следующий момент она есть K'. Тогда конфигурация K' называется непосредственно выводимой из К (обозначение К ╞ K'). Если К ₁ — начальная конфигурация, то последовательность где при , называется тъюринговым вычислением. При этом говорят, что конфигурация К_т выводима из конфигурации , и пишут . Если К_т явля­ется к тому же заключительной конфигурацией, то говорят, что К_т заключительно выводима из К ₁, и пишут .

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

Если — исходное слово, то машина Т, начав работу «на сло­ве» , либо остановится через определенное число шагов, либо ни­когда не остановится. В первом случае говорят, что машина Т при­менима к слову и результатом применения машины Т к слову является слово Р, соответствующее заключительной конфигурации (обозначение ). Во втором случае говорят, что машина Т не применима к слову .

В дальнейшем мы будем предполагать, если не оговаривается противное, что: 1) исходное слово непустое, 2) в начальный момент головка находится против самой левой непустой ячейки на ленте и 3) машина начинает работу, находясь в состоянии .

Зоной работы машины Т (на слове )называется множество всех ячеек, которые за время работы машины хотя бы один раз обозреваются головкой.

Часто будет использоваться обозначение для слов ви­да (m раз), где ; при считаем, что — пустое слово; если — слово длины 1, то вместо (т раз) и будем писать

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

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

. Приведенное выражение надо понимать так: машина «стирает» слово и останавливается на первой букве слова W; если же W — пустое слово, то «останов» происходит на втором 0 (нуле) после слова .

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

Пример 1. Выяснить, применима ли машина Тьюринга Т, за­даваемая программой П, к слову Р. Если применима, то выписать результат применения машины Т к слову Р (считается, что — на­чальное состояние и в начальный момент головка машины обозревает самую левую единицу на ленте):

a) б) .

Решение. а) Исходя из конфигурации получаем после­довательно такие конфигурации: Так как команды вида в программе П нет, то последняя конфигурация (т.е. ) заключительная. Сле­довательно, машина Т к слову применима, и .

б) Выписывая конфигурации, имеем и т.д. Яс­но, что этот процесс продолжается неограниченно. Значит, машина Т к слову не применима.

Пример 2. Построить в алфавите {0, 1} машину Тьюринга, которая применима к словам вида и но не применима к словам вида и . (К словам иного вида машина может быть как применима, так и не применима.)

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

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

Поэтому оба состояния и «сменим»: рассмотрим коман­ды .

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

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

Если же первый единичный массив четный, а второй нечетный, то на первый нуль после второго массива головка выйдет в состоянии , и машина не должна остановиться. Поэтому берем команду . Аналогично рассматривается случай с нечетным первым единичным массивом.

Подходящая машина задается программой