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

Пусть имеются две МТ: М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(MT) =

. . .

Естественно, что не все натуральные числа являются номерами каких-то МТ. Но если 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

Определение. МТ называется самоприменимой, если она применима к своему номеру N(M), т. е. если она начинает работу со своим кодом и через конечное число шагов останавливается (заканчивает работу).

Очевидный пример несамоприменимой машины – если в правых частях команд не встречается q0 – stop – состояние. Такая машина не применима ни к какому слову, а не только к N(M).

Рассмотрим алгоритмическую проблему самоприменимости, т. е. существует ли алгоритм, который по любому N(M) устанавливает, самоприменима ли она или нет. Согласно Тьюрингу это означает, существует ли такая МТ, которая была бы применима к кодам номеров всех МТ и в зависимости от того, самоприменима МТ или нет, имела бы различные заключительные конфигурации. Например, в случае самоприменимости МТ заключительная конфигурация имеет вид {00 10 0}, а в случае несамопри-

менимости {0 0 00 0}.

Теорема. Проблема самоприменимости алгоритмически неразрешима, т. е. не существует МТ, решающей эту проблему.

Доказательство. Предположим противное, что такая машина А существует. Тогда можно построить машину В, которая: 1) применима ко всем кодам номеров несамоприменимых машин, т. е. по номеру устанавливает, что машина несамоприменима; 2) не применима ко всем кодам номеров самоприменимых машин.

Действительно, машина В получается из А следующим образом: алфавит сохраняется неизменным; заключительное состояние q0 машины А считается незаключительным состоянием В, а заключительным состоянием В считается новое состояние , причем программа В состоит из всех команд А и еще двух команд:

1q0 -> 1Cq0

0q0 -> 0C

Очевидно, что В удовлетворяет требованиям 1) и 2), так как конфигурация 1 машины А означает, что установлена самоприменимость иссле-

дуемой МТ, а команда 1q0 -> 1Cq0 зацикливает программу, что означает, что В не применима к номеру самоприменимой МТ; в то же время заключительная конфигурация 0 машины А устанавливает несамоприме-

нимость МТ, а команда 0q0 -> 0C означает, что В применима к несамоприменимой МТ.

16