Материал: Красовская Т. Ф. Основы теории алгоритмов

В зависимости от того, какая была подана начальная информация A, т. е. какая была начальная конфигурация, возможны 2 случая.

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

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

2. МТ не останавливается, т. е. не переходит в состояние q0, как говорят, «зацикливается». В таком случае говорят, что данная МТ не применима к информации A.

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

{a1, a2, …a … an}

q

Это означает, что до a1 и после an ячейки пустые, т. е. в них стоят a0, а в ячейках a1, . . ., an могут быть как нулевые, так и ненулевые символы внешнего алфавита.

При этом машина находится в состоянии qj.

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

aiqj -> ak(R, L, C )qs

Здесь 5 символов, 2 – из внешнего, 3 – из внутреннего алфавитов. Такой шаг означает, что символ ai в ячейке, возле которой стоит управляющая головка, заменяется на символ ak, МТ из состояния qj переходит в состояние qs и при этом головка или сдвигается на 1 клетку вправо (R) или влево (L) или остается на месте (C).

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

Рассмотрим в качестве примера тьюрингову схему.

11

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

МТ останавливается, она переработала слово a2 a2 в слово a2 a2 a2. Пусть теперь начальная конфигурация:

Как видим, процесс, т. е. конфигурации, начали повторяться, т. е. МТ «зациклилась», следовательно, данная МТ не применима к начальной ин-

формации {a0 a1 a1 a2 a2 a0 }.

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

Этот тезис, так же как и тезис Чёрча, нельзя доказать, так как он связывает нестрогое понятие алгоритма со строгим определением МТ. Его можно опровергнуть, если удастся привести пример алгоритма, который не может быть реализован с помощью МТ. Однако все известные до сих пор алгоритмы могут быть заданы посредством МТ.

12

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

Определение. Функция y = f(x1, x2, . . . xn) называется вычислимой по Тьюрингу, если существует МТ с алфавитом {0, 1}такая, что при начальной конфигурации, задающей в алфавите МТ значения x1, x2 . . . xn

({0 1 1 1 0 1 110 111 1 0}), МТ начинает работу и, если при таких значе-

ниях функция y определена, то МТ заканчивает работу в конфигурации, определяющей значение y:

({0 0 1 1111 0 0}).

Теорема. Функции, вычислимые по Тьюрингу, есть частично-рекур- сивные функции, и наоборот.

Докажем, что простейшие ПРФ O(x) = 0; S(x) = x + 1; Im (x1 ... xn) = xm есть функции, вычислимые по Тьюрингу.

1. O(x) ≡ 0 МТ{0, 1} для вычисления этой функции задается тьюринговой схемой с двумя состояниями {q0, q1}:

q1 0Cq0 0Lq1

2. S(x) = x + 1 МТ {0, 1} c состояниями {q0, q1} для этой функции задается Тьюринговой схемой:

q1 1Cq0 1Lq1

Посмотрим, как работает эта МТ: {0 0 1 1 0 0}

{0 0 1 1 0 0}

{0 0 1 1 0 0}

{0 0 1 1 0 0} stop

13

3. I1(x1 . . . xn) = x1; x1 ≠ 0

МТ {0, 1} с состояниями {q0, q1, q2, q3, q4, q5} задается тьюринговой схемой:

МТ остановилась в конфигурации, дающей значение x1.

14

Композиция МТ

Пусть имеются две МТ: М1 и М2 с общим алфавитом А. М1 описывается состояниями {q1, q2 . . . qm, q0}; M2 – { , . . . , , }. Образуем новую МТ, являющуюся композицией М1 и М2, следующим образом: вместо

q0 записываем = qm + 1 = qm + 2 . . . = qm + n. Получаем машину

М2(М1) с алфавитом А и состояниями {q1, . . , qm, qm + 1, . . ., qm + n, }. – заключительное состояние этой машины. Эта машина сначала работает как

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

Геделева нумерация МТ

Каждая МТ по определению есть набор М(А, Q, П),

где А – внешний алфавит с выделенным пустым символом a0,

Q – внутренний алфавит состояний с выделенными символами конечного (q0) и начального (q1) состояний,

П – программа, т. е. конечная последовательность упорядоченных пя-

терок символов aikqjk -> ask Stk qrk; k = 1, 2 . . . n, где S0 – R; S1 – L; S2 – C.

Существуют некоторые обширные алфавиты A0 и Q0, в которых записываются все упомянутые символы.

Пусть p1, p2, p3 ... – последовательность всех простых чисел, расположенных в порядке возрастания, т. е. последовательность 2, 3, 5, 7, 11, 13 ...

Номером МТ назовем число:

Естественно, что не все натуральные числа являются номерами каких-то МТ. Но если N – номер какой-то МТ в алфавите A0, Q0, то ее программу можно однозначно восстановить по ее номеру.

Примеры

1. МТ {0, 1} для вычисления функции S(x) = x + 1 П: 1q1 -> 1Rq1

0q1 -> 1Cq0 Номер этой МТ: N = 21315170111130171191232290 = 56386110.

2. Пусть N(MT) = 62734386 =2·31367193 = 2·3·10455731 =

=2·3·11·950521 = 2·3·11·11·86411 = 2·3·11·11·13·6647 = 2·3·11·11·13·17·391 =

=2·3·11·11·13·17·17·23 = 21·31·50·70·112·131·172·190·231·29.

Тогда программа этой МТ: 1q1 -> 0Rq2

1q2 -> 0Lq0

15