Рекурсивные и рекурсивно перечислимые

Цели урока

• Различать Recursive и RE: decider vs recognizer, гарантия остановки
• Понимать теорему Recursive = RE пересечение co-RE и её доказательство через параллельный запуск
• Объяснять технику dovetailing и зачем она нужна для перечислителей
• Применять классификацию к конкретным задачам: halting problem, теоремы, синтаксис

Предварительные знания

• Turing Machine: Formal Definition

Facebook, 2012. Команда безопасности пишет статический анализатор Infer для поиска null dereference в Java-коде Instagram. Infer находит баги - но иногда зависает на сложных циклах. Это не баг Infer: для произвольного кода разрешимого детектора не существует. Граница между RE и Recursive - это граница между «иногда зависает» и «всегда даёт ответ».

• **Статический анализ кода:** инструменты вроде ESLint/SonarQube работают с разрешимыми подмножествами проверок. Полная верификация - неразрешима
• **Антиспам/антивирус:** RE-подход: если нашли вирус - сообщаем. Если не нашли - не значит, что его нет. Разрешимого детектора не существует
• **Theorem provers:** для некоторых теорий (арифметика Пресбургера) проверка разрешима. Для полной арифметики - только RE

Клини, Пост и рождение рекурсивной иерархии

В 1943 году Эмиль Пост из City College of New York опубликовал статью о «нормальных системах» - эквиваленте машин Тьюринга. Он первым ввёл понятие перечислимо-рекурсивного множества (recursively enumerable set) и показал существование множеств, которые RE, но не рекурсивны - задолго до того, как стало ясно, что это и есть проблема остановки. Стивен Клини в том же году формализовал рекурсивные функции. Вместе они заложили иерархию Поста - полную классификацию языков по вычислимости, которую изучают до сих пор.

Рекурсивные (разрешимые) языки

**Идеальный судья: получает вопрос - всегда отвечает «да» или «нет».** Никогда не зависает, не уходит «подумать навечно». Именно так работает машина Тьюринга для **разрешимого** (рекурсивного) языка.

**Рекурсивный (разрешимый) язык** - это язык L, для которого существует TM M (decider), такая что: для любого w в Σ*, M(w) = accept если w в L, и M(w) = reject если w не в L. Ключевое: M **всегда останавливается**.

Разрешимые языки - «комфортный» класс. Для них можно написать программу, которая для **любого** входа даст точный ответ за конечное время. Все задачи из обычного программирования (сортировка, поиск, парсинг) - разрешимые.

**Важное свойство:** разрешимые языки замкнуты относительно объединения, пересечения, дополнения и конкатенации. Если L1 и L2 разрешимы, то L1 U L2, L1 пересечение L2, дополнение L1 и L1·L2 тоже разрешимы.

Рекурсивно перечислимые (RE) языки

**Ненадёжный судья**: если ответ «да» - скажет. Если ответ «нет» - может думать вечно, и результат никогда не придёт. Это **рекурсивно перечислимый** (RE) язык.

**Рекурсивно перечислимый язык** (RE, Turing-recognizable) - это язык L, для которого существует TM M, такая что: M(w) = accept если w в L, а если w не в L, то M может reject ИЛИ зависнуть навсегда.

**Асимметрия «да»/«нет»** - ключевая черта RE-языков. Принадлежность можно подтвердить (если строка в языке - машина примет), но не опровергнуть (если строка не в языке - ждём вечно).

Дополнение и теорема о связи RE и Recursive

Если умеешь и подтверждать, и опровергать принадлежность строки языку - значит, умеешь **разрешать** его. Формально: язык L рекурсивен тогда и только тогда, когда и L, и его дополнение L̄ оба рекурсивно перечислимы.

**Теорема:** L в Recursive тогда и только тогда, когда L в RE и L̄ в RE. Другими словами: Recursive = RE пересечение co-RE.

Ключевой трюк в доказательстве - **параллельный запуск**. Чередуем шаги M1 и M2 (один шаг M1, один шаг M2, ...). Поскольку w принадлежит либо L, либо L̄, одна из машин гарантированно остановится.

Из этой теоремы следует: если L в RE, но L не в Recursive, то **L̄ не в RE**. Дополнение проблемы остановки - язык зависающих программ - не является даже рекурсивно перечислимым! Нельзя написать программу, которая гарантированно найдёт зависание.

**Следствие для практики:** невозможно написать программу, которая обнаруживает бесконечные циклы в произвольном коде. Язык «зависающих программ» - не RE, даже частичного распознавателя нет.

Перечислители и dovetailing

Почему «рекурсивно **перечислимые**»? Потому что их элементы можно **перечислить** - напечатать один за другим. Не обязательно по порядку, не обязательно без повторов, но каждый элемент рано или поздно появится в списке.

**Перечислитель** (enumerator) - это TM с принтером. Работает бесконечно и периодически печатает строки. Язык перечислителя - множество всех напечатанных строк. Теорема: L рекурсивно перечислим тогда и только тогда, когда существует перечислитель для L.

**Dovetailing** (чередование, «ласточкин хвост») - техника для параллельной симуляции бесконечного числа вычислений. На шаге k делаем по одному шагу для первых k вычислений. Если какое-то из них завершится - это будет замечено.

Без dovetailing запуск M1 заблокирует всё: если M1 зависает - **никогда** не перейдём к M2. Dovetailing решает эту проблему, справедливо распределяя время между всеми вычислениями.

Ключевые идеи

• **Рекурсивные (разрешимые):** TM-decider всегда останавливается. Замкнуты относительно всех операций, включая дополнение
• **RE (полуразрешимые):** TM может зависнуть на «нет». Асимметрия: умеем подтверждать, не умеем опровергать
• **Recursive = RE пересечение co-RE:** язык разрешим тогда и только тогда, когда и он, и его дополнение - RE. Параллельный запуск двух TM даёт decider
• **Dovetailing:** техника чередования бесконечного числа вычислений, позволяющая не застрять на зависшей машине

Связанные темы

Классификация языков по вычислимости - основа для понимания границ алгоритмов:

• Машина Тьюринга — Формальная модель, через которую определяются классы RE и Recursive
• Вычислимые функции — Тотальные вычислимые функции соответствуют разрешимым языкам, частичные - RE
• Иерархия Хомского — RE-языки = тип 0 в иерархии, контекстно-свободные и регулярные - строгие подмножества

Вопросы для размышления

• Почему параллельный запуск двух RE-распознавателей (для L и L̄) даёт decider? Что гарантирует, что один из них остановится?
• Как dovetailing связан с понятием справедливой планировки (fair scheduling) в операционных системах?
• Если бы можно было решить проблему остановки - какие практические инструменты для программистов стали бы возможны?

Связанные уроки

• comp-02 — Формальная модель TM, на которой строится понятие decider/recognizer
• comp-01 — Вычислимые функции: тотальные соответствуют Recursive, частичные - RE
• comp-04 — Редукции между языками строятся на классификации RE и Recursive
• fl-01-intro — RE-языки = тип 0 иерархии Хомского, верхний уровень формальных языков
• fl-20-church-turing — Тезис Чёрча-Тьюринга определяет пределы Recursive-класса
• cplx-01 — Классы P и NP лежат внутри Recursive - полезный контраст
• alg-01 — Алгоритмическая разрешимость - конкретизация свойства decider