Теорема Райса и свойства РП-языков

Неразрешимость языков L_e и L_ne есть только частный случай более общей теоремы о неразрешимости любого нетривиального свойства РП-языков.

Свойством РП-языков называют множество РП-языков. Например, свойства “быть контексно-свободным языком” или “быть регулярным языком” представлены соответственно множествами контекстно-свободных и регулярных языков. Тривиальным свойством называют множество из одного пустого языка или из всех РП-языков. В противном случае свойство называют нетривиальным.

Пусть Ã - свойство РП-языков, а L_Ã - множество кодов машин M_i

таких, что L(M_i) ÎÃ.

Теорема (Райса).Всякое нетривиальное свойство РП-языков неразрешимо.

Доказательство. Пусть Ã - свойство РП-языков и (ÆÏÃ) Ú (ÆÎÃ).

a) Допустим, что ÆÏÃ, тогда существует непустой язык LÏÃ, пусть xÎL. Построим алгоритм, сводящий L_u к L_Ã . По паре (M,w) строится машина M ^’ такая, что (M,w)Î L_u « M ^’ Î L_Ã:

Если (M,w) Ï L_u, т.е. M не допускает вход w, тогда M ^’ прекращает работу, не допуская свой вход x. L(M^’ ) = Æ, следовательно,

L(M ^’ ) ÏÃ, а M^’ Ï L_Ã. Если (M,w) Î L_u, то L(M^’ ) = L и M^’ Î L_Ã.

Схема такого алгоритма приведена на рис.

Машина M^’ имеет две ленты: на первой записан код машины M и входа w, на второй – код машины M_L , допускающей язык L.

Работа моделируемой машины M^’ состоит в следующих шагах:

1. Имитируется работа универсальной машины U на входе (M,w).

2. Если (M,w) Ï L _u, т.е. M не допускает вход w, то M^’ прекращает работу, не допуская свой вход x.

3. Если (M,w) Î L _u, т.е. M допускает w, то далее M^’имитирует работу машины M_L на входе x и допускает, так как xÎL и M_L допускает язык L.

Таким образом, для рассматриваемого свойства Ã, где ÆÏÃ,

L_u < L_{Ã ,} следовательно, язык L_Ã неразрешим.

b) Допустим, что ÆÎÃ. Рассмотрим Ã, дополнение свойства Ã, т.е. множество РП-языков, не обладающих свойством Ã. Свойство Ã содержит Æ, так что как в части a) можно доказать неразрешимость языка L_Ã . Поскольку язык L_Ã есть множество кодом машин, не допускающих свойство Ã, то L_Ã = L_Ã . Если предположить, что язык L_Ã разрешимый, то по теореме Поста, его дополнение - рекурсивный язык, что не верно. “

Неразрешимые проблемы, связанные с языками машин Тьюринга:

1. Пуст ли язык, допускаемый машиной Тьюринга?

2. Конечен ли язык, допускаемый машиной Тьюринга?

3. Регулярен ли язык, допускаемый машиной Тьюринга?

4. Контекстно-свободен язык, допускаемый машиной Тьюринга?

Разрешимые (тривиальные) проблемы, связанные с языками машины Тьюринга:

1. Содержит ли машина Тьюринга данное число состояний?

2. Существует ли вход, допускаемый машиной Тьюринга за данное число переходов?

Упр.