Разрешимые и неразрешимые языки 4 февраля 2014 г



Pdf просмотр
Дата05.04.2017
Размер20.6 Kb.
Просмотров485
Скачиваний0

Разрешимые и неразрешимые языки
4 февраля 2014 г.
1. Назовем язык беспрефиксным, если ни одно его слово не является пре- фиксом другого. Докажите, что следующий язык разрешим:
{R | R — регулярное выражение, а L(R) — беспрефиксный язык}.
2. Разрешим ли следующий язык: {( M , w, c) | M — машина Тьюринга,
которая в процессе обработки входного слова w однажды записывает на ленту символ c}?
Решение: Нет, этот язык неразрешим. Предположим иное. Пусть N — машина
Тьюринга, разрешающая этот язык. Тогда можно построить машину
H, разрешающую язык A
TM
. Получив на вход описание машины C и слово w, машина H строит описание машины M , работающей так же,
как C, но перед переходом в допускающее состояние записывающей на ленту некоторый символ c, отсутствующий в алфавите машины C.
Затем машина H запускает машину N на входе ( M , w, c) и возвраща- ет ее ответ. Очевидно, что C допускает w в том и только том случае,
если M , будучи запущенной на слове w, напишет на ленте символ c.
Таким образом, H разрешает язык A
TM
, который однако неразрешим.
Следовательно, машины N не существует.
3. Докажите, что у языка {1}

есть неразрешимое подмножество.
Решение: Неразрешимый язык A
TM
был нами определен над алфавитом {0, 1}

и является множеством двоичных строк. Воспользовавшись вычисли- мой функцией unary : {0, 1}

→ {1}

, переводящей двоичную запись числа в унарную, определим
A
1
TM
= {unary(1w) | w ∈ A
TM
}.
Очевидно, что разрешимость A
1
TM
означала бы разрешимость A
TM
:
машина для A
TM
могла бы просто приписать к входной строке еди- ницу, перевести полученную строку в унарную кодировку и передать результат машине для A
1
TM
. Следовательно, A
1
TM
⊆ {1}

неразрешим.
4. Докажите, что ни язык
{( M , N ) | M, N — машины Тьюринга и L(M ) ⊆ L(N )},
ни его дополнение не распознаваемы по Тьюрингу.
1

Решение: Предположим, что этот язык распознаваем, и S — машина Тьюринга,
которая его распознает. Тогда машина H, разрешающая A
TM
может работать следующим образом. Получив на вход описание машины C
и слово w, она строит описание машины T
w
, допускающей слово w и отвергающей все прочие слова, и машины T
¯
w
, отвергающей слово w и допускающей все прочие слова. Очевидно, что или L(T
w
) ⊆ L(C)
и C допускает w, или L(C) ⊆ T
¯
w и C отвергает w. Машина H па- раллельно запускает две копии машины S: одна копия получает на вход ( T
w
, C ), вторая — ( C , T
¯
w
). Параллельная работа двух ко- пий может быть достигнута, например, за счет использования двух лент (но мы знаем, что для любой многоленточной машины можно построить эквивалентную ей одноленточную). Так как L(T
w
) ⊆ L(C)
или L(C) ⊆ T
¯
w
, одна из копий машины S обязательно остановится и выдаст положительный ответ. Если положительный ответ будет полу- чен от первой копии, то C допускает w, если от второй, то не допускает.
Машина H разрешает язык A
TM
, что невозможно.
Доказательство нераспознаваемости дополнения языка из условия за- дачи можно провести аналогично.
5. По теореме Райса всякий язык P , состоящий из описаний машин Тью- ринга и обладающий следующими двумя свойствами, неразрешим:
(a) P содержит некоторые, но не все описания машин Тьюринга;
(b) для любых двух машин Тьюринга M
1
и M
2
, разрешающих один и тот же язык L(M
1
) = L(M
2
), имеет место
M
1
∈ P ⇐⇒
M
2
∈ P.
Объясните, почему одного из этих двух свойств недостаточно, чтобы гарантировать неразрешимость P .
Решение: Любой язык вида { M }, где M — машина Тьюринга, обладает свой- ством (a), но является разрешимым. Язык ∅ обладает свойством (b),
но также разрешим.
2

Каталог: data -> 2014
2014 -> Особенности проведения маркетИнговых исследований для новых товаров
2014 -> Программа исследования 28
2014 -> Специализированный журнал автомобильной тематики: специфика аудитории, контента, продвижения на рынок
2014 -> Федеральное государственное автономное образовательное
2014 -> Программа «Управление образованием»
2014 -> Приложения выберите пункт Электронная почта
2014 -> Клиент-серверная система на основе беспроводной сети стандарта ieee 802. 15. 4
2014 -> Гринкруг Ефим Михайлович (должность, звание) подпись (Ф. И. О.) (Дата) Москва, 2014 г реферат


Поделитесь с Вашими друзьями:


База данных защищена авторским правом ©nethash.ru 2019
обратиться к администрации

войти | регистрация
    Главная страница


загрузить материал