Информатика · объяснение и практика
Теорема Райса относится к смыслу программы: синтаксический тест остаётся другой задачей
Распознать нетривиальное семантическое свойство вычислимой частичной функции и правильно применить неразрешимость, не распространяя её на свойства текста программы.

В теме Методы алгоритмов: углубление · Учебная карта
Главная мысль
Теорема Райса запрещает общий решающий алгоритм для любого нетривиального свойства вычисляемой частичной функции. Свойство должно зависеть от поведения, а не от конкретной записи программы. Проверка числа символов в исходнике под это утверждение не попадает.
Метод и постановка
Проверьте два условия отдельно. Семантичность означает, что программы с одинаковым вычисляемым поведением имеют одинаковый ответ на вопрос. Нетривиальность означает существование хотя бы одной вычислимой функции со свойством и хотя бы одной без него. Если свойство выполняется для всех программ или ни для одной, постоянный ответ уже решает задачу.
Уточните модель поведения. В классической формулировке программа задаёт частичную функцию: на некоторых входах вычисление может не завершиться. «Возвращает ноль хотя бы на одном входе» относится к такой функции, а «содержит букву z» относится к тексту. Две разные записи могут вычислять одну функцию, поэтому свойства текста нельзя автоматически объявить семантическими.
Проверка и границы вывода
Идея сведения состоит в том, чтобы встроить неизвестное вычисление в новую программу. Пока оно не завершилось, новая программа ведёт себя одним способом; после завершения может воспроизвести поведение, отличающееся по интересующему свойству. Универсальный решатель свойства тогда помог бы решить уже известную неразрешимую задачу. Полное доказательство следит за тем, какое поведение имеет нигде не определённая функция и какую из двух альтернатив нужно выбрать.
Вывод не запрещает полезные анализаторы ограниченных классов программ. Конечные автоматы, ограниченные циклы или заранее заданное конечное множество входов меняют область задачи. Также возможны односторонние процедуры, которые находят подтверждение для части случаев, но могут не закончиться на остальных. Неразрешимость общего решателя не равна невозможности доказать свойство конкретной программы вручную. В формулировке ответа всегда сохраните квантор «для всех программ указанной модели» и требование обязательного завершения алгоритма.
Пример
Свойство «на входе ноль программа завершается и возвращает пять» семантично и нетривиально. Постоянная функция пять его имеет, постоянная функция шесть не имеет. Общий решатель для произвольных программ невозможен.
Вопрос «исходник содержит более ста символов» решается простым подсчётом текста. Он может меняться при добавлении пробелов без изменения вычисляемой функции, поэтому теорема Райса к нему не относится.
От чтения к действию
А теперь — вы
Частые вопросы
Теорема запрещает анализ конечного автомата?
Нет. У конечной модели отдельные семантические свойства могут решаться полным обходом состояний.
Нетривиальное означает сложное?
Нет. Это точное условие: свойство есть хотя бы у одной функции и отсутствует хотя бы у одной другой.
Углублённый разбор
Полурешение семантического свойства программы
Неразрешимость семантического свойства не исключает односторонний поиск подтверждения. Если положительный ответ имеет конечное вычислительное свидетельство, его можно найти диагональным исполнением всех возможных кандидатов.
Перед началом: Частичная вычислимая функция; Сведение задачи остановки.
Полурешатель обязан завершаться только на положительных входах
Рассмотрим свойство P: программа возвращает число семь хотя бы на одном натуральном входе. Положительный ответ подтверждается парой: конкретный вход x и конечное число шагов t, за которое вычисление закончилось с нужным результатом. Свидетельство можно проверить конечной симуляцией. Отрицание требует исключить все входы и все времена, что не даёт такого же конечного поиска.
Полурешатель P должен когда-нибудь принять каждую программу со свойством и никогда не принимать программу без него. На отрицательных входах он может работать бесконечно. Это отличается от решателя, который обязан завершиться с верным «да» или «нет» на каждом входе. Поэтому отсутствие найденного свидетельства за заданное время не является доказанным отрицательным ответом.
Диагональный обход не даёт одному зависанию остановить поиск
На стадии s симулируйте первые s шагов программы на каждом входе от нуля до s. Если обнаружено завершение с семью, примите программу. Любое настоящее свидетельство (x,t) попадёт в проверку не позднее стадии max(x,t). Все стадии конечны, поэтому поиск завершится на каждом положительном случае. Повторная симуляция допускается: она неэффективна, но достаточна для доказательства вычислимости процедуры.
Последовательная схема «сначала дождаться входа ноль, затем входа один» неверна. Если нулевой вход зациклился, следующие входы вообще не будут рассмотрены. Диагональное распределение конечного бюджета между всеми кандидатами устраняет именно эту проблему. Оно не угадывает время завершения и не превращает бесконечное ожидание в отрицательный результат.
Почему общего решателя всё равно не существует
По экземпляру остановки M(y) построим Q(x): сначала симулировать M(y), а если оно завершилось, вернуть семь. Тогда Q имеет свойство P ровно при остановке M(y). Построение текста Q эффективно и не требует знать исход симуляции. Решатель P решил бы задачу остановки, что невозможно. Это самостоятельное сведение устанавливает границу найденного полурешателя.
Дополнение P тоже не может иметь полурешатель. Иначе запустили бы оба полурешателя вперемежку: один обязательно подтвердит верную сторону, и получится общий решатель. Этот аргумент использует взаимную исключительность и полноту двух ответов. Нельзя заменить второй полурешатель произвольной эвристикой, иногда сообщающей об отсутствии результата.
Поздний вход при раннем бесконечном цикле
Условие. Программа на входе 0 не завершится; на 1 выдаёт 5 за один шаг; на 2 выдаёт 4 за четыре шага; на 3 выдаёт 7 за два шага. Когда диагональный поиск впервые найдёт свидетельство?
- На стадии 1 проверяются входы 0 и 1 с бюджетом один. Нужного результата нет: первый ещё работает, второй возвращает пять.
- На стадии 2 добавляется вход 2, но его бюджет недостаточен для завершения. Вход 3 пока не рассматривается.
- На стадии 3 рассматривается вход 3 с бюджетом три. Его завершение за два шага с результатом семь обнаруживается.
- Таким образом, принимающая стадия равна трём. Последовательное ожидание входа ноль никогда не добралось бы до этого конечного свидетельства.
Ответ. Диагональный полурешатель принимает на стадии 3 со свидетельством (3,2).
Проверка. Независимая конечная модель завершений проверяет каждую стадию; общее доказательство охвата использует s≥max(x,t), а не данный набор четырёх входов.
Где легко ошибиться. Тайм-аут поиска не означает отрицания семантического свойства. Полурешение гарантирует обнаружение существующего конечного свидетельства, но не обязательное завершение на отрицательных случаях.
Проверьте понимание
Вопросы к этой главе
Можно не перезапускать симуляции?
Да, можно хранить состояния всех начатых вычислений и выдавать им по шагу. Доказательство требует справедливого распределения, чтобы каждый фиксированный вход получил неограниченный бюджет.
Свойство P синтаксическое?
Нет. Оно зависит от значений вычисляемой частичной функции. Добавление комментария или переименование переменных его не меняет, хотя конкретный синтаксис программы может измениться.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Boaz Barak: Universality and uncomputability
Прочитаны невычислимость HALT, направление сведения и границы теоремы Райса; упражнение 9.10 указывает на рекурсивную перечислимость. Собственные процедуры диагонального поиска и сведения на тотальных программах доказаны отдельно. Численные тесты не выдаются за машинное доказательство неразрешимости.
Обещание завершения ограничивает входы задачи
Обещание завершения меняет область задачи анализа программ. Оно позволяет решить вопрос о результате на фиксированном входе, но не делает автоматически разрешимыми свойства поведения сразу на всех натуральных входах.
Перед началом: Тотальная и частичная функция; Задача с обещанием.
Алгоритм использует обещание, а не проверяет его
Предположим, на вход анализа подаются только программы, завершающиеся на каждом натуральном x. Для вопроса «возвращает ли P(0) нуль?» достаточно запустить P(0), дождаться результата и сравнить его с нулём. На обещанной области процедура всегда заканчивается. Вне области она может зависнуть; это не нарушение требований задачи с обещанием.
Отсюда не следует алгоритм распознавания тотальности произвольной программы. Обещание является условием входа, предоставленным извне. Анализатор не обязан и в общем случае не может предварительно подтвердить его для каждого текста. Поэтому вывод «теорема Райса запрещает любой такой тест» слишком широк: после ограничения области её исходная формулировка уже не применяется автоматически.
Универсальное свойство остаётся трудным даже для тотальных программ
Рассмотрим другой вопрос: P(x)=0 для всех натуральных x. По произвольному вычислению M(y) создадим тотальную программу T(n), которая симулирует M(y) не больше n шагов. Если завершение обнаружено, T возвращает единицу, иначе нуль. Каждое вычисление T конечно, независимо от того, завершится ли M(y) когда-нибудь.
Если M(y) никогда не останавливается, T тождественно нулевая. Если M(y) останавливается за t шагов, то T(n)=1 для всех n≥t. Поэтому решатель тождественного нуля даже только на обещанно тотальных программах решил бы дополнение задачи остановки, а значит и саму остановку после инверсии ответа. Ограничение области в этом случае не устраняет неразрешимость.
Фиксированный вход и бесконечная область требуют разных кванторов
Для одного заданного x обещание обеспечивает завершение ровно той симуляции, которую нужно провести. Для всех x не существует последнего проверяемого входа. Программа может возвращать нуль на сколь угодно длинном начальном отрезке и впервые выдать единицу позднее. Проверка миллиона входов не становится доказательством универсального свойства без дополнительной структуры программы.
При конечной заранее заданной области входов универсальный вопрос решается последовательным запуском всех случаев, если завершение обещано на каждом. Это ещё одно изменение условий задачи. В отчёте полезно явно написать область, обещание и квантор свойства; иначе положительный вывод для одного входа легко ошибочно расширить на бесконечное множество.
Конечная симуляция внутри тотальной программы
Условие. Пусть M(y) останавливается ровно на пятом шаге. Для построенной T(n) с бюджетом n шагов вычислите T(0),…,T(6) и объясните роль неизвестного времени остановки.
- При n=0,1,2,3,4 симуляция ещё не обнаруживает завершение. Поэтому первые пять значений T равны нулю.
- При n=5 и n=6 завершение обнаружено. Оба значения равны единице; каждый запуск T всё равно заканчивается после конечного бюджета.
- Если бы M(y) не завершалась, все значения T были бы нулевыми. Именно эти два случая различал бы предполагаемый решатель тождественного нуля.
- Длинный нулевой префикс ничего не доказывает об остальных входах: время остановки M может превышать любой заранее выбранный конечный предел.
Ответ. Значения равны 0,0,0,0,0,1,1; T тотальна в обоих случаях исходной остановки.
Проверка. Модель ограниченной симуляции проверяет пороговые значения и конечность каждого запуска. Сведение в тексте рассматривает также случай отсутствия остановки и произвольное конечное t.
Где легко ошибиться. Обещание тотальности не является её проверкой и не устраняет бесконечный квантор «для всех входов». Разные свойства на обещанной области могут иметь разную разрешимость.
Проверьте понимание
Вопросы к этой главе
Можно решить P(7)=0 вместо P(0)=0?
Да, для любого фиксированного входа используется тот же запуск и сравнение при обещании завершения. Число семь не меняет логический тип задачи.
А если известна конечная граница всех входов?
Тогда можно проверить каждый вход в этой конечной области. Такой вывод относится к конечной задаче и не переносится на все натуральные числа.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Boaz Barak: Universality and uncomputability
Прочитаны невычислимость HALT, направление сведения и границы теоремы Райса; упражнение 9.10 указывает на рекурсивную перечислимость. Собственные процедуры диагонального поиска и сведения на тотальных программах доказаны отдельно. Численные тесты не выдаются за машинное доказательство неразрешимости.
Теорема рекурсии Клини: программа с собственным индексом
Программа может использовать собственное описание без внешнего оракула. Теорема рекурсии формулирует это как неподвижную точку вычислимого преобразования программ. Разберём конструкцию индекса и объясним, почему совпадает поведение программ, а не обязательно их числовые коды.
Перед началом: Нумерация программ и универсальное вычисление; Частичная вычислимая функция и генератор программы.
Неподвижная точка относится к вычисляемой функции
Зафиксируем приемлемую нумерацию частично вычислимых функций: φe — функция программы с индексом e. Для любого всюду определённого вычислимого преобразования индексов F существует e с φe=φF(e). Равенство означает одинаковые значения там, где вычисления определены, и одинаковую неопределённость на остальных входах. Условие e=F(e) не требуется.
Генератор F должен завершаться и выдавать корректный индекс для каждого e. При этом сгенерированная программа может не завершаться на некотором входе. Это различие между построением текста программы и её запуском существенно: компилятор может быстро выдать описание вычисления, которое потом работает бесконечно. Теорема не является алгоритмом решения проблемы остановки.
Конструкция через параметризацию программы
Построим всюду вычислимый генератор σ(x), выдающий индекс программы: на входе y сначала вычислить φx(x), затем запустить программу с полученным индексом на y. Само построение σ(x) завершается, хотя исполнение полученной программы может зависнуть уже на первом этапе. Возможность вставить x в шаблон программы обеспечивается параметризацией, известной как s-m-n.
Пусть t — индекс всюду вычислимой функции x↦F(σ(x)), и положим e=σ(t). По определению генератора φe(y)=φφt(t)(y). Но φt(t)=F(σ(t))=F(e), поэтому φe(y)=φF(e)(y). В этом выводе не понадобилось заранее угадывать числовой индекс e: само применение программы к собственному описанию организовано конструкцией σ.
Полезное применение и граница вывода
Выберем F(e) как индекс программы, которая игнорирует вход и возвращает e+7. Такой генератор можно построить обычной вставкой числовой константы в шаблон. Теорема даёт программу с некоторым индексом e, возвращающую e+7 на любом входе. Она получает нужную информацию структурой своего описания, а не перебором всех индексов с проверкой их поведения.
Конкретное числовое значение e зависит от принятой нумерации и генератора кода; без их задания честный ответ остаётся символическим. Полезный вывод состоит в существовании и конструктивном получении программы нужного поведения. Смена формата исполняемых файлов или системы нумерации меняет код, но не превращает семантическую неподвижную точку в обязательное числовое равенство кодов.
Программа возвращает свой индекс плюс 7
Условие. Преобразователь F(e) выдаёт программу с постоянным результатом e+7. Используя σ(x) и t из объяснения, постройте семантическую неподвижную точку и определите её результат на произвольном входе y.
- Генератор σ(x) создаёт программу y↦φφx(x)(y). Он строит описание, а не выполняет вложенные вычисления.
- Функция x↦F(σ(x)) всюду вычислима; выбираем её индекс t и задаём e=σ(t).
- Получаем цепочку φe(y)=φφt(t)(y)=φF(σ(t))(y)=φF(e)(y).
- По выбранному определению F последняя программа возвращает e+7 независимо от y. Следовательно, так же работает программа с индексом e.
Ответ. e=σ(t) является семантической неподвижной точкой. На каждом входе она возвращает e+7; числовой индекс без системы кодирования не определяется.
Проверка. Внутреннее вычисление φt(t) завершается, поскольку функция с индексом t всюду определена. Далее запускается сгенерированная постоянная программа; она также завершается. Для других F последний вывод о завершении уже не следовал бы автоматически.
Где легко ошибиться. Не заменяйте равенство поведения φe=φF(e) требованием равенства числовых индексов e=F(e).
Проверьте понимание
Вопросы к этой главе
Нужно ли программе читать свой исполняемый файл?
Не обязательно. В доказательстве сведения о собственном описании возникают через генератор кода и универсальное вычисление. Конкретный механизм зависит от модели программирования.
Почему это не решает проблему остановки?
Теорема строит программу с определённой самоссылочной связью. Она не сообщает, завершится ли произвольная вложенная программа; частичная неопределённость допускается в самом утверждении.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Ryan Williams, MIT6.045: The Recursion Theorem, лекция 12
Формулировка возможности использовать собственное описание. Индексная конструкция через σ и пример преобразователя постоянной программы развёрнуты самостоятельно.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Как состояние вершины помогает обнаружить цикл ориентированного графа
Ищем цикл ориентированного графа по состояниям вершин, отличаем активную ветвь от уже законченной и не принимаем любое повторное посещение за доказательство цикла.
Открыть темуЛемма о накачке: разбиение выбирает противник, а степень выбираете вы
Построить корректное доказательство нерегулярности языка по лемме о накачке, сохраняя порядок кванторов и охватывая все допустимые разбиения.
Открыть темуКак конечный автомат хранит только нужное состояние истории
Создаём автомат чётности единиц, выписываем переходы и объясняем, какую информацию о прочитанной части строки можно забыть.
Открыть тему