Перечислимость и выводимость

Множество формальных теорем, т. е. выводимых формул, в формальной системе с разрешимыми множествами аксиом и правил вывода обладает более слабым алгоритмическим свойством — перечислимостью.

Определение 4.66. 2-ленточная МТ перечисляет язык L С А*, если она, работая на пустом входе, печатает на одной из лент (выходная лепта) список всех слов языка L (возможно, с повторениями), разделённых специальным знаком # ^ А. При этом машина никогда не изменяет непустые символы на выходной ленте.

Язык называется перечислимым, если какая-то машина его перечисляет.

Можно охарактеризовать перечислимые множества условиями, которые ослабляют условия для разрешимых множеств.

Определение 4.67. Пусть для языка L в конечном алфавите А существует такая решающая МТ с алфавитом В D А, которая останавливается в состоянии q_yGii в точности на входах из языка L. (При этом пустой символ, А не принадлежит алфавиту А.) Тогда будем говорить, что такая машина допускает язык L.

Из этого определения сразу следует, что для любого разрешимого множества существует допускающая машина. Обратное, вообще говоря, неверно: машина, которая допускает L, может не останавливаться на одном из входов, не принадлежащих L.

Теорема 4.68. Язык перечислим тогда и только тогда, когда некоторая машина Тьюринга допускает его.

Доказательство. Пусть для языка L есть перечисляющий алгоритм. Опишем допускающую L машину (многоленточную). Она запускает перечисляющий алгоритм и после печати очередного слова сравнивает напечатанное слово и то слово, которое ей подано на вход. В случае совпадения допускающая машина останавливается в состоянии q_yes, иначе продолжает выполнение перечисляющего алгоритма. Поскольку перечисляющий алгоритм печатает в точности слова из языка L, допускающая машина останавливается в состоянии q_yes в точности на входах из L.

И в обратную сторону: пусть машина М допускает язык L. Перечисляющий алгоритм работает итерациями. На итерации с номером i он проверяет для каждого из первых г слов гщ,…, Wi в алфавите А (порядок лексикографический) остановится ли машина М на входе Wj за г тактов работы в состоянии q_yes. Если обнаруживается слово, для которого это условие выполнено, оно печатается на выходную ленту.

Такой алгоритм печатает только слова из языка L. С другой стороны, на каждом слове из языка L машина М останавливается в состоянии </<sub>yes. Поэтому каждое слово из L будет рано или поздно напечатано. ?

Следствие 4.69. Пересечение перечислимого и разрешимого множест. ва перечислимо.

Доказательство. Пусть множество А разрешается машиной Mi, а множество В допускается машиной М2. Машина М, которая допускает язык А П В, использует машины Mi и М2 следующим образом. Вначале она сохраняет копию входного слова и запускает Mi. Если работа Mi заканчивается в состоянии с/no? то машина М также останавливается в отвергающем состоянии. Если работа Mi заканчивается в состоянии </<sub>yes, то машина М запускает М2 на сохранённой копии входного слова. ?

Для перечислимых множеств есть несколько других характеризаций.

Задача 4.24. Докажите, что язык L А* перечислим тогда и только тогда, когда.

• (а) L является проекцией разрешимого множества, т. е. существует такое разрешимое множество R С (Ли{#})*, # ^ Л, что w € L равносильно существованию такого и € R, что и =
• (б) L является областью определения некоторой вычислимой функции, т. е. множеством тех слов, на которых останавливается некоторая машина Тыоринга;
• (в) L является областью значений некоторой всюду определённой вычислимой функции, т. е. существует такая машина Тыориига, которая останавливается на любом входе, а результаты её работы в точности совпадают с языком L.

Задача 4.25. Докажите, что если слова языка L можно перечислить в лексикографическом порядке, то язык L разрешим.

Теорема 4.70. Если множество аксиом и правила вывода формальной системы разрешимы, то множество выводимых в этой формальной системе формул перечислимо.

Доказательство. Перечисляющий алгоритм работает следующим образом. Он перебирает все слова в лексикографическом порядке и для каждого слова проверяет, является ли оно описанием вывода. Если найдено слово, которое является описанием вывода, то алгоритм печатает описания всех формул, входящих в этот вывод.

Ясно, что такой алгоритм напечатает только выводимые формулы. С другой стороны, для каждой выводимой формулы F есть вывод, описание которого является конечным словом. Поэтому перечисляющий алгоритм рано или поздно обработает это слово и напечатает F. ?

Задача 4.26. Докажите, что если формулы, аксиомы и правила вывода формальной системы перечислимы, то множество выводимых в этой формальной системе формул также перечислимо.

Указание: используйте результат задачи 4.24(a).

Замечание 4.71. Из этих фактов можно сделать вывод, что из иеперечислимости некоторого множества слов сразу следует, что нельзя построить такую формальную систему, в которой выводятся в точности слова из этого множества, а множества формул, аксиом и правил вывода перечислимы.

В дальнейшем окажется очень полезной связь между перечислимостью и разрешимостью, устанавливаемая следующей теоремой.

Теорема 4.72 (Пост). Если язык L и его дополнение A*L перечислимы, то язык L разрешимы.

Доказательство. В одну сторону теорема тривиальна: дополнение к разрешимому множеству разрешимо. Чтобы доказать её в обратную сторону, рассмотрим алгоритм Z), который выполняет поочерёдно алгоритмы, перечисляющие множество и его дополнение (на разных лентах) и сравнивает каждое из напечатанных слов со своим входом. Если вход совпал со словом, которое напечатал алгоритм, перечисляющий L, то алгоритм D останавливается в состоянии q_yes, если вход совпал со словом, которое напечатал алгоритм, перечисляющий дополнение к L, то алгоритм D останавливается В СОСТОЯНИИ (/по;

Поскольку любое слово будет напечатано на одной из лент, алгоритм D всегда останавливается. ?

Из теоремы Поста получаем примеры неперечислимых множеств: это дополнения к неразрешимым перечислимым множествам.

Задача 4.27. Докажите перечислимость множества описаний машин Тьюринга, останавливающихся на пустом входе.

Указание: используйте теорему 4.68.

Из этой задачи и теоремы Поста следует, что множество описаний тех машин Тьюринга, которые не останавливаются на пустом входе, неперечислимо. То же самое справедливо и для других универсальных моделей вычислений. Важный для дальнейшего случай сформулируем явно.

Следствие 4.73. Неперечислимо множество описаний лшшин Минского, которые не останавливаются, начиная работу с нулевыми регистрами.