Языки и трансляции. Мартыненко Б.К. - 92 стр.

UptoLike

ВУЗ: 

СПбГУ | Санкт-Петербург

Составители: 

Рубрика: 

91
Было бы уместно дать следующее разумное объяснение термина “диагона-
лизация”. Можно перенумеровать все слова в множестве Σ
*
следующим
образом. Взять сначала самые короткие, и среди слов равной длины
использовать некоторый лексикографический порядок. Затем мы можем
занумеровать автоматы типа 1 согласно номерам, приписанным их кодам.
Автомат A принимает i-е слово тогда и только тогда, когда i-е слово не
принимается i-м автоматом. Вообразим бесконечную матрицу, элемент
которой (i, j) есть 1, если i-й автомат принимает j-е слово, и 0 — в противном
случае. Автомат A принимает i-е слово, когда элемент (i, i) есть 0. Отсюда и
термин “диагонализация”.
6.2.7. Подпрограммы.
Одна машина Тьюринга может быть
“подпрограммой” другой машины Тьюринга при весьма общих условиях.
Если T
1
должна быть подпрограммой для T
2
, мы требуем, чтобы их состояния
не пересекались. Но с состояниями других подпрограмм состояния T
1
могут
пересекаться.
Чтобы “вызвать” T
1
, машина T
2
входит в начальное состояние машины T
1
.
Правила машины T
1
являются частью правил машины T
2
. Кроме того, из
состояния остановки машины T
1
, машина T
2
входит в свое собственное
(возвратное) состояние и продолжает работу.
Пример 6.6. Опишем неформально машину Тьюринга T
3
, которая
вычисляет n! Именно, машина, запущенная с входной цепочкой вида
01
n
0
,
должна заканчивать работу с кодом вида 0
n +2
1
n!
на непустой части ее ленты.
Машина T
3
использует машину T
2
в качестве подпрограммы, которая
выполняет умножение. Именно, машина T
2
, запущенная с входной цепочкой
вида 01
i
0
j
1
k
на ее ленте и ленточной головкой на крайнем левом нуле блока из j
нулей, останавливается с результатом вида 01
i
0
j
1
ik
.
Из своей начальной конфигурации машина T
3
,
двигаясь вправо, проходит
блок единиц и последний нуль, печатает 1 и движется влево. В этот момент на
ленте машины T
3
находится цепочка 01
n
01. Далее машина T
3
вызывает
подпрограмму T
2
. Когда управление вернется к машине T
3
, ее лента будет
содержать цепочку 01
n
01
n
0. Затем из своего текущего состояния машина T
3
проверяет, остаётся ли в первом блоке, по крайней мере, три единицы. Если это
так, она изменяет крайнюю правую единицу в этом блоке на нуль и
возвращается в состояние, из которого она вызывает подпрограмму T
2
.
После второго вызова подпрограммы T
2
на ленте машины T
3
появится
цепочка 01
n–1
001
n (n–1)
0. После третьего вызова на ленте будет последователь-
ность 01
n–2
0001
n (n–1)(n –2)
0, и вызовы T
2
будут повторяться до тех пор, пока после
(n –1)-го вызова на ленте не появится цепочка 0110
n–1
0001
n (n–1) (n – 2) ...2
0. В это
время первый блок единиц имеет меньше трёх 1, так что машина T
3
изменяет их
на нули и останавливается при состоянии ленты 0
n+2
1
n(n–1)(n–2)...2
0 = = 0
n +2
1
n!
0.
В свою очередь, машина T
2
сама использует машину T
1
в качестве своей
подпрограммы, которая, располагая двумя блоками единиц, добавляет первый
блок, не изменяя его, ко второму. При построении машины T
1
пригодится
метод отметки посредством символов “отключения проверки”. Машина T
2

Страницы