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

UptoLike

ВУЗ: 

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

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

Рубрика: 

111
Рассмотрим язык L
1
= {x
i
| x
i
не принимается Tm T
i
}. Язык L
1
не приниматся
никакой Tm. Действительно, если бы это не было так, то существовала бы
некоторая машина Тьюринга, скажем T
j
, которая бы принимала язык L
1
.
Возьмем, цепочку x
j
.
Пусть x
j
∈ L
1
. По определению языка x
j
не принимается машиной T
j
.
С другой стороны, машина T
j
распознает язык L
1
, стало быть принимает
x
j
∈L
1
. Наше допущение привело к противоречию.
Пусть теперь x
j
∉ L
1
. Машина T
j
распознает язык L
1
, стало быть x
j
не
принимается машиной T
j
, но по определению языка x
j
принимается машиной T
j
.
Опять противоречие. Остаётся признать, что язык L
1
не принимается никакой
Tm.
Предположим, что мы имели бы алгоритм (т.е. машину Тьюринга, которая
всегда останавливается) для определения, остановится ли когда-нибудь
машина Тьюринга в данной конфигурации. Обозначим этот алгоритм T
0
. Тогда
мы могли бы построить машину Тьюринга T, которая принимает язык L
1
, а это
противоречило бы только что установленному факту. Машина T действовала
бы следующим образом:
1. Пусть x∈L
1
на её входе. Прежде всего, она перечисляет предложения x
1
,
x
2
, ... до тех пор, пока не обнаружит, что некоторое x
i
= x. Таким образом, Tm T
определяет, что x является i-м предложением в этом перечислении.
2. Затем Tm T генерирует код машины Тьюринга T
i
.
3. Управление теперь передаётся машине T
0
, которая может определить,
останавливается Tm T
i
с входной цепочкой x
i
или нет.
4. Если T
0
устанавлила, что Tm T
i
не останавливается с входной цепочкой x
i
(т. е. Tm T
i
не принимает x
i
), то машина T останавливается и принимает x
i
.
5. Если же T
0
устанавлила, что Tm T
i
останавливается с входной цепочкой x
i
,
то управление передаётся универсальной машине Тьюринга, которая
моделирует машину T
i
с входной цепочкой x
i
.
6. Поскольку, как было выяснено на предыдущем шаге, Tm T
i
останавливается с входной цепочкой x
i
, то универсальная машина Тьюринга
остановится и определит, принимает машина T
i
цепочку x
i
или нет. В любом
случае Tm T останавливается, принимая x
i
в случае, когда Tm T
i
цепочку x
i
не
принимает, и наоборот, отвергая x
i
, если Tm T
i
её принимает.
Итак, наше предположение о том, что существует машина Тьюринга,
которая всегда останавливается и решает проблему остановки произвольной
машины Тьюринга, привела нас к противоречию, состоящему в том, что мы
сумели построить машину Тьюринга, распознающую язык L
1
. Это даёт
возможность сформулировать следующее утверждение.
Теорема 7.1. Не существует алгоритма (машины Тьюринга, которая
гарантированно останавливается) для определения, остановится ли в конце
концов произвольная машина Тьюринга, начиная в произвольно заданной
конфигурации.
Доказательство вытекает из подходящей формализации вышеприведён-
ного рассуждения.
Для многих проблем не существует разрешающего алгоритма, в частности
и для решения некоторых проблем, касающихся теории языков.

Страницы