Математическая теория формальных языков
Разрешимые и перечислимые множества
Определение 14.2.1.
Говорят, что детерминированная машина Тьюринга
с выделенным состоянием qa
разрешает (decides) язык , если
1) для каждого слова
найдутся такие
и , что ;
2) для каждого слова
найдутся такие
и , что . Состояние qa
называется допускающим (принимающим, accept state), состояние qr
называется отвергающим (непринимающим, (reject state).
Пример 14.2.2.
Рассмотрим детерминированную машину Тьюринга
где , , , , , ,
и
Эта машина Тьюринга разрешает язык .
Определение 14.2.3.
Язык L над алфавитом
называется разрешимым или рекурсивным (decidable, recursive), если существует детерминированная машина Тьюринга
(с выделенным состоянием qa), которая разрешает язык L.
Определение 14.2.4.
Говорят, что машина Тьюринга
допускает (принимает, accepts) слово , если для некоторых
и
.
Определение 14.2.5.
Язык, допускаемый машиной Тьюринга M, - это язык, состоящий из всех допускаемых данной машиной Тьюринга слов.
Определение 14.2.6.
Язык называется перечислимым (рекурсивно перечислимым, полуразрешимым, recursively enumerable), если существует детерминированная машина Тьюринга, допускающая этот язык.
Замечание 14.2.7.
В определении 14.2.6 можно отбросить требование детерминированности машины Тьюринга.
Теорема 14.2.8.
Каждый разрешимый язык является перечислимым.
Доказательство. Пусть дана машина Тьюринга
с выделенным состоянием qa, которая разрешает язык . Тогда машина Тьюринга
допускает язык L.
Пример 14.2.9.
Если в машине Тьюринга из примера 14.1.15 заменить переход
на , то получится машина Тьюринга, допускающая язык . Следовательно, этот язык является перечислимым. Можно доказать, что он даже является разрешимым.
Теорема 14.2.10.
Существует такая машина Тьюринга над однобуквенным алфавитом , что язык, допускаемый этой машиной Тьюринга, неразрешим.
Доказательство. Доказательство существования перечислимого неразрешимого множества можно найти, например, в [31, 9.2].
Упражнение 14.2.11.
Найти детерминированную машину Тьюринга с входным алфавитом {a}, разрешающую язык .
Упражнение 14.2.12.
Найти детерминированную машину Тьюринга с входным алфавитом {a}, допускающую язык
