Конспект: диагональ, проблема останова, сведения и неразрешимое вне программ

Понятия

Счётное множество - элементы можно занумеровать числами 0, 1, 2, …; иначе множество несчётно. Диагональный приём - по списку строится объект, отличающийся от n-го элемента в n-м месте.

Проблема останова - по тексту программы и входу сказать, остановится ли она.

Сведение A к B - всегда останавливающийся алгоритм, превращающий входы A во входы B с сохранением ответа. Теорема Райса - любое нетривиальное свойство поведения программ неразрешимо.

Надёжный анализатор не пропускает ошибок; полный не даёт ложных тревог.

Проблема соответствий Поста - есть ли ряд костей с одинаковыми верхней и нижней надписями. Усердный бобёр BB(n) - наибольшее число шагов останавливающейся машины с n состояниями.

Что унести

СЧЁТНО                                НЕСЧЁТНО
целые числа, пары (по диагоналям)     бесконечные двоичные
                                      последовательности
строки: пустая, 0, 1, 00, 01, 10, …   языки (ответ «да/нет»
программы и машины (это строки)       для каждой строки)

номер строки: приписать 1 слева, прочитать как число, вычесть 1
              101 → 1101 = 13 → 12
диагональ на таблице 8 × 8:  10100100  отличается от строки i в знаке i;
                             дописали - нашлась новая
программ счётно, языков несчётно
    →  почти все языки не распознаёт ни одна программа

ПРОБЛЕМА ОСТАНОВА
def naoborot(P):
    if ostanavlivaetsya(P, P):   работать вечно
    else:                        остановиться
naoborot(naoborot):  остановилась → предсказано «нет» → не должна;
                     и наоборот - противоречие

таблица «Pᵢ на тексте Pⱼ»: naoborot отличается от каждой Pᵢ на диагонали,
                           а сама должна быть в списке
распознаваема (выполнить и дождаться), не разрешима;
дополнение не распознаваемо

лента фиксированной длины: конфигураций конечно,
                           повтор = не остановится - вопрос разрешим
  туда-сюда: повтор на шаге 11
  счётчик 2, 4, 6, 8 разрядов: 12, 58, 248, 1014 шагов, повторов нет
  8 клеток, 2 символа, 4 состояния:  4 · 8 · 2⁸ = 8192 конфигурации
бесконечная лента: конфигурации не повторяются - приём не срабатывает

СВЕДЕНИЯ
A сводится к B,  A неразрешима   →   B неразрешима
сводят ИЗВЕСТНУЮ трудную задачу К новой;  наоборот - ничего не доказывает

останов → «напечатает ли слово»:  выполнить P на x;  print("готово")
останов → «достижима ли строка»:  выполнить P на x;  помеченная строка
останов → «равны ли программы»:   первая как выше, вторая просто печатает
строится только ТЕКСТ, P не запускается

теорема Райса:  поведение - неразрешимо       текст - разрешимо
                возвращает ли 7 на входе 5     длиннее ли ста строк
                останавливается ли всегда      есть ли слово while

АНАЛИЗАТОР ЗНАКОВ: надёжный, не полный
делитель        анализ        на деле
x² + 1          чисто         чисто
x²              замечание     падает при x = 0
x² − 4          замечание     падает при x = ±2
x² + 2 − 1      замечание     чисто - ложная тревога:
                              о разности известны только знаки
промолчал - ошибки нет ни при каком x;   ругается - может быть, зря

ВНЕ ПРОГРАММ
домино Поста:
  b/ca  a/ab  ca/a  abc/c  →  ряд из 5 костей, abcaaabc,
                              найден на 636-й проверке
  100/1  0/100  1/00       →  до длины 6 пусто (1092 ряда),
                              решение - 7 костей
  ab/a  b/ab               →  решения нет: после первой кости
                              продолжить нечем
«не найдено до L» ничего не говорит про L + 1
останов → Пост → однозначность КС-грамматики, равенство грамматик,
                 пустота пересечения
целые корни многочлена от нескольких переменных: алгоритма нет (1970)

BB(n):   1    6    21    107    47 176 870     пятое значение доказано
                                               в 2024 году
знать BB(n) = уметь решать останов для машин с n состояниями
    →  функция не вычислима

Теорема о рекурсии даёт неподвижную точку поведения при вычислимом преобразовании описаний. Колмогоровская сложность - длина кратчайшей печатающей программы на фиксированной универсальной машине; она невычислима.

Ловушки джокера

Дописал пропущенную строку в список и успокоился. Диагональ применима и к исправленному списку.

Счёл неразрешимое долгим. У долгой задачи алгоритм есть.

Решил, что теорема запрещает анализировать конкретную программу. Запрещён единый метод для всех.

Свёл свою задачу к проблеме останова. Направление обратное: останов - к своей задаче.

Применил теорему Райса к свойству текста. Число строк и ключевые слова проверяются точно.

Прочитал молчание ненадёжного анализатора как «ошибок нет». Так можно читать только надёжный, и только про его класс ошибок.

Счёл ложные тревоги багом анализатора. У надёжного они неизбежны.

Принял «перебор не нашёл» за «решения нет». Решение могло быть на следующей длине.

Назвал функцию вычислимой, потому что известны её первые значения. Нужен алгоритм для всех n.

Проверь себя

Почему программ счётное число, а языков несчётное, и что из этого следует? Как устроена программа «наоборот» и почему её запускают на собственном тексте? Почему при ограниченной памяти вопрос об останове решается? В какую сторону идёт сведение при доказательстве неразрешимости? Что обещает надёжный анализатор и чем за это платит? Почему перебор распознаёт задачу Поста, но не разрешает её?

Понятия

Что унести

Ловушки джокера

Проверь себя

Комментарии

Оставить комментарий