Вычислимость и тест Тьюринга

На ленте записано двоичное число 1011. Нужно прибавить единицу. Человек сразу пишет 1100; маленькая машина тратит восемь шагов. Мы увидим каждый из них. Затем зададим машине вопрос о другой программе: «Ты когда-нибудь остановишься?» Тут уже не спасут ни миллиарды операций в секунду, ни бесконечное терпение. Наконец, попросим человека отличить машинный ответ от человеческого. Ответ снова окажется не абсолютным, но причина будет совсем иной.

Во всех трёх опытах решает точность обещания. Первая процедура обещает прибавить единицу и завершиться на любой конечной двоичной строке. Гипотетический анализатор обещает решить остановку для каждой программы и каждого входа. Судья в имитационной игре обещает различать два источника с некоторой измеримой точностью. Слова «любой», «всегда» и «с вероятностью» нельзя менять местами. От них зависит, что мы вправе заключить.

Сначала исполним восемь шагов

Машина Тьюринга состоит из ленты, головки и конечного набора состояний. Лента разбита на клетки. В каждой клетке лежит символ из конечного алфавита; в нашем примере это 0, 1 или пустой знак ·. Головка видит одну клетку. Состояние $q$ хранит малую часть памяти, которая не записана на ленте.

Один переход имеет вид

$$\delta(q,s)=(q',s',d).$$

Здесь $q$ означает текущее состояние, $s$ прочитанный символ, $q'$ следующее состояние, $s'$ записываемый символ, а $d\in\{L,R,S\}$ задаёт ход влево, вправо или остановку на месте. В каждый момент исполняется ровно одна строка таблицы $\delta$. Если строки для пары $(q,s)$ нет, вычисление тоже можно считать остановившимся, хотя в учебном примере мы используем отдельное состояние $q_{\mathrm{halt}}$.

Для прибавления единицы хватит двух рабочих состояний. В $q_{\mathrm{scan}}$ головка идёт вправо до первой пустой клетки. После неё машина возвращается влево в состоянии $q_{\mathrm{carry}}$ и переносит единицу через хвост из единиц:

$$\begin{aligned} \delta(q_{\mathrm{scan}},0)&=(q_{\mathrm{scan}},0,R),\\ \delta(q_{\mathrm{scan}},1)&=(q_{\mathrm{scan}},1,R),\\ \delta(q_{\mathrm{scan}},\mathord{\cdot})&=(q_{\mathrm{carry}},\mathord{\cdot},L),\\ \delta(q_{\mathrm{carry}},1)&=(q_{\mathrm{carry}},0,L),\\ \delta(q_{\mathrm{carry}},0)&=(q_{\mathrm{halt}},1,S),\\ \delta(q_{\mathrm{carry}},\mathord{\cdot})&=(q_{\mathrm{halt}},1,S). \end{aligned}$$

Последняя строка нужна для входов 1, 11, 111 и так далее. Перенос доходит левее старшего разряда и создаёт новый разряд. Поэтому 1111₂ превращается в 10000₂, а лента должна иметь пустые клетки с обеих сторон.

Конфигурация хранит весь текущий мир машины

Чтобы воспроизвести вычисление, мало записать строку на ленте. Нужны состояние и позиция головки. Будем заключать символ под головкой в квадратные скобки:

0  q_scan   · [1] 0  1  1  ·
1  q_scan   ·  1 [0] 1  1  ·
2  q_scan   ·  1  0 [1] 1  ·
3  q_scan   ·  1  0  1 [1] ·
4  q_scan   ·  1  0  1  1 [·]
5  q_carry  ·  1  0  1 [1] ·
6  q_carry  ·  1  0 [1] 0  ·
7  q_carry  ·  1 [0] 0  0  ·
8  q_halt   ·  1 [1] 0  0  ·

Строка с номером $t$ показывает конфигурацию до перехода $t+1$. Между строками 4 и 5 машина читает пустую клетку, оставляет её пустой и начинает перенос. Между строками 7 и 8 она читает первый ноль слева от хвоста единиц, записывает единицу и останавливается. На ленте остаётся 1100.

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

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Инвариант объясняет, почему ответ верен

Покадровая трасса доказывает результат лишь для 1011. Для произвольной строки нужен инвариант, то есть свойство, которое сохраняется на каждом шаге выбранной фазы. Пусть вход содержит $n$ битов и кодирует число $N$.

В состоянии $q_{\mathrm{scan}}$ лента не меняется, а головка после $j$ шагов стоит над битом с индексом $j$ либо над правой пустой клеткой. Поэтому после $n$ шагов она обязательно достигнет пустого символа. Ещё один переход переводит машину в $q_{\mathrm{carry}}$.

Пусть справа у числа стоят $r$ единиц подряд. Во время переноса уже обработанный суффикс состоит из $k$ нулей, где $0\le k\le r$. Биты левее головки пока совпадают со входом. Каждый переход по единице увеличивает $k$ на один и сдвигает головку влево. Когда встречается ноль, он превращается в единицу; когда $r=n$, вместо нуля встречается пустая клетка и тоже превращается в единицу. В обоих случаях получена обычная двоичная запись $N+1$.

Число шагов можно посчитать точно:

$$T(n,r)=n+1+r+1=n+r+2,\qquad 0\le r\le n.$$

Минимум близок к $n+2$, если последний бит равен нулю. Максимум равен $2n+2$ на строке из одних единиц. Значит,

$$n+2\le T(n,r)\le 2n+2, \qquad T(n,r)=\Theta(n).$$

Это первый маленький анализ алгоритма в курсе. Мы доказали остановку, правильность результата и линейную границу времени. Ни один из трёх выводов не следует просто из того, что несколько запусков закончились удачно.

Лаборатория, где нельзя спрятать шаг

Выберите вход 1011₂ и восемь раз нажмите «Шаг». После каждого нажатия сравнивайте четыре объекта: золотую клетку, состояние над головкой, подсвеченную строку таблицы и последнюю строку трассы. Все четыре должны описывать одну конфигурацию. Кнопка «Пуск» исполняет те же переходы с паузой; это визуальный режим, а не другой алгоритм.

Затем запустите 1111₂. Машина сделает десять шагов, потому что $T(4,4)=10$, и создаст 10000₂. Наконец, сравните 0100₂ и 0₂. Ведущий ноль сохраняется как клетка ленты, хотя числовое значение можно было бы записать короче. Так проявляется разница между строкой и числом: программа работает с кодом, а смысл кода задаём мы.

От одной машины к понятию алгоритма

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

Частичная функция $f$ называется вычислимой по Тьюрингу, если существует машина, которая на входе $x$ останавливается с результатом $f(x)$ всякий раз, когда $f(x)$ определено. Если машина зациклилась, значение считают неопределённым. Для тотальной функции требуется остановка на каждом допустимом входе:

$$\forall x\in X\quad \exists t<\infty: \operatorname{Run}(M,x,t)=f(x).$$

Знак $\forall$ здесь сильнее миллиона тестов. Тесты проверяют конечное множество $x_1,\ldots,x_m$; определение говорит обо всём $X$, которое часто бесконечно.

Разные формальные модели пришли к одному классу вычислимых функций: $\lambda$-исчисление Чёрча, рекурсивные функции, машины Тьюринга и нормальные алгоритмы Маркова. Перевод между моделями может быть неудобным и медленным, но он сохраняет сам факт вычислимости.

Тезис, полнота и конкретная программа

Три близкие фразы отвечают на три разных вопроса.

Тезис Чёрча–Тьюринга утверждает: всякая функция, которую можно вычислить эффективной механической процедурой, вычислима машиной Тьюринга. Это тезис, а не обычная теорема. Левая часть использует доформальное слово «эффективная», поэтому её нельзя вывести внутри одной формальной системы. Сильное основание тезиса состоит в совпадении многих независимо придуманных моделей и в десятилетиях практики программирования.

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

Вычислимость конкретной функции требует программы и доказательства её поведения. Из полноты Python не следует, что написанная на Python функция сортирует список или хотя бы завершается. Полнота говорит «в языке можно выразить»; корректность говорит «эта программа делает обещанное».

Код программы тоже помещается на ленте

Таблица переходов конечна, поэтому её можно закодировать строкой. Присвоим состояниям и символам номера, запишем каждую пятёрку $(q,s,q',s',d)$ двоичными блоками и разделим блоки служебным кодом. Получится описание $\langle P\rangle$. Универсальная машина $U$ принимает пару

$$U(\langle P\rangle,x)$$

и шаг за шагом имитирует $P(x)$. Программа для $U$ фиксирована; меняются описание $P$ и вход $x$. Такой переход отделяет устройство от программы. Интерпретатор Python, эмулятор старой приставки и виртуальная машина используют тот же общий приём, хотя их инженерная реализация намного богаче ленты.

Описание можно подать самой описанной программе. В выражении $P(\langle P\rangle)$ нет самосознания: это обычный запуск на строке. Копирование собственного файла, компилятор, читающий исходный код компилятора, и тест, проверяющий собственную конфигурацию, дают земные аналоги.

В уроке 03 мы видели, что строка данных хранит происхождение измерения. Здесь строка хранит процедуру. В обоих случаях синтаксис сам по себе не сообщает семантику: договорённость о коде связывает байты с объектом.

Обещание идеального анализатора

Хотелось бы написать программу $H$, которая заранее отвечает, завершится ли другая программа. Сначала зафиксируем обещание полностью. Пусть $\mathrm{Prog}$ означает множество конечных кодов программ, а $\mathrm{Input}$ множество конечных входных строк. Мы предполагаем существование вычислимой тотальной функции

$$H:\mathrm{Prog}\times\mathrm{Input}\to\{0,1\}$$

со свойством

$$\forall P\in\mathrm{Prog}\;\forall x\in\mathrm{Input}: \quad \begin{cases} H(P,x)=1,&\text{если }P(x)\text{ останавливается},\\ H(P,x)=0,&\text{если }P(x)\text{ работает бесконечно}. \end{cases}$$

Слово «тотальная» означает ещё один квантор:

$$\forall P\;\forall x\;\exists t<\infty: H(P,x)\text{ выдаёт ответ к шагу }t.$$

Время $t$ может зависеть от $P$ и $x$. От $H$ не требуют общей быстрой границы. Разрешены часы и миллиарды лет; запрещено только вечное молчание. Именно это делает последующее противоречие утверждением о вычислимости, а не о скорости.

Программа, которая доверяет прогнозу и делает наоборот

Предположим, что $H$ существует. Построим программу $D$ с одним входом $y$:

D(y):
    если H(y, y) = 1:
        повторять пустой шаг вечно
    иначе:
        остановиться

$D$ получает ответ, потому что $H$ по предположению тотален. После этого она выбирает поведение, противоположное прогнозу для программы $y$ на входе $y$. Пусть $d=\langle D\rangle$ означает код самой $D$. Запустим $D(d)$.

Есть ровно два окончательных ответа $H(d,d)$.

Если $H(d,d)=1$, анализатор предсказывает остановку $D(d)$. По первой ветви $D$ входит в вечный цикл. Предсказание ложно.

Если $H(d,d)=0$, анализатор предсказывает бесконечную работу $D(d)$. По второй ветви $D$ сразу останавливается. Предсказание снова ложно.

Формально получены две импликации:

$$\begin{aligned} H(d,d)=1&\Rightarrow D(d)\uparrow,\\ H(d,d)=0&\Rightarrow D(d)\downarrow, \end{aligned}$$

где $\uparrow$ означает бесконечный запуск, а $\downarrow$ остановку. Но обещание $H$ требует обратных соответствий. Любой из двух ответов противоречит этому обещанию.

Рис. 4.2 нужен не для украшения уже готового доказательства. Он проверяет полноту разбора случаев: слева показан ответ «да», справа ответ «нет», а нижние блоки сравнивают каждое предсказание с фактом.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Что доказательство запрещает, а что оставляет

Неразрешимость не означает, что каждая проверка остановки безнадёжна. Программа for i in range(100): ... очевидно конечна. Анализатор может доказать остановку для языка без неограниченных циклов, найти простой зацикленный участок или попросить программиста указать убывающую меру.

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

1. ограничим язык конечными циклами;
2. разрешим ответ «не знаю»;
3. допустим вероятностный прогноз с измеряемой ошибкой;
4. запросим доказательство от автора программы.

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

Сюда же относится тестирование. Миллион завершившихся запусков подтверждает миллион входов. Он не доказывает квантор $\forall x$. Формальное доказательство может закрыть бесконечное семейство, если использует инвариант или убывающую меру, как в двоичном инкременте. Но автоматический поиск такого доказательства для произвольной программы снова упирается в границы вычислимости.

«Да» иногда можно подтвердить без решающего алгоритма

Разрешимость требует двух конечных исходов. Для языка $L$ нужен алгоритм, который всегда останавливается и отвечает

$$x\in L\Rightarrow 1,\qquad x\notin L\Rightarrow 0.$$

Распознаваемость, или полуразрешимость, слабее. Распознаватель обязан принять элемент языка за конечное время, но на чужом элементе может отвергнуть его или работать бесконечно:

$$x\in L\Rightarrow R(x)\downarrow=1,\qquad x\notin L\Rightarrow R(x)\uparrow\ \text{или}\ R(x)\downarrow=0.$$

Множество останавливающихся пар

$$K=\{(P,x):P(x)\downarrow\}$$

распознаваемо. Достаточно симулировать $P(x)$ и принять пару, когда симуляция закончится. Если $P(x)$ не остановится, свидетельство «да» никогда не появится. Эта процедура не решает $K$, но каждое положительное утверждение подтверждает конечной трассой.

Есть красивый критерий. Если язык $L$ и его дополнение $\overline L$ распознаваемы, то $L$ разрешим. Запустим два распознавателя по очереди: один шаг первого, один шаг второго, снова шаг первого. Ровно один из них когда-нибудь примет вход, после чего получен ответ. Такой режим называют параллельной симуляцией или «ласточкиным хвостом».

$$L\ \text{распознаваем и}\ \overline L\ \text{распознаваем} \quad\Longrightarrow\quad L\ \text{разрешим}.$$

Из неразрешимости $K$ следует, что дополнение $\overline K$ не может быть распознаваемым. Иначе два распознавателя дали бы запрещённый решатель остановки.

Рис. 4.3 разводит три обещания. Поиск делителя у натурального числа имеет конечную границу $\sqrt n$ и решает оба исхода. Симуляция $P(x)$ подтверждает только остановку. Тотальный $H$ обещал больше и оказался невозможен.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Медленно и невозможно лежат по разные стороны

Теперь вернём время в картину. Алгоритм полного перебора всех двоичных строк длины $n$ всегда заканчивается после $2^n$ вариантов. Он вычислим и разрешает конечный вопрос, но ресурс растёт очень быстро.

При скорости $10^9$ операций в секунду идеализированное время равно

$$t(n)=\frac{2^n}{10^9}\ \text{с}.$$

Десять дополнительных битов умножают число вариантов не ровно на тысячу, а на

$$\frac{2^{n+10}}{2^n}=2^{10}=1024.$$

Для $n=20$ получаем около $1{,}05$ миллисекунды. При $n=40$ требуется $1099{,}5$ секунды, или $18{,}3$ минуты. При $n=60$ выходит около $36{,}5$ года. Для $n=80$ результат близок к $38{,}3$ миллиона лет. Эти оценки намеренно игнорируют память и обмен данными, поэтому они оптимистичны.

Рис. 4.4 использует логарифмическую вертикальную шкалу. На ней экспонента выглядит прямой, потому что $\log_2 2^n=n$. Подписи возвращают физический масштаб и не дают принять прямую линию за медленный рост.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Тайм-аут не решает проблему остановки

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

$$\{\text{остановилась},\ \text{найден цикл},\ \text{неизвестно после }10\text{ с}\}.$$

Третий исход смешивает две ситуации. Программа могла войти в вечный цикл, а могла закончить на одиннадцатой секунде. Увеличение тайм-аута переносит границу, но не создаёт безошибочный ответ для всех программ.

То же происходит при ограниченной проверке моделей. Если система не решила задачу за минуту, эксперимент сообщает отказ в заданном бюджете. Он не доказывает неспособность при любом бюджете. В уроке 01 модель была частью системы с порогом и маршрутом отказа; здесь тайм-аут играет такую же системную роль.

Тьюринг меняет вопрос

В 1950 году Алан Тьюринг открыл статью Computing Machinery and Intelligence фразой: “I propose to consider the question, ‘Can machines think?’” Статья вышла в журнале Mind, том 59, номер 236, страницы 433–460. Уже на первой странице автор предлагает заменить спор о значении слов наблюдаемой игрой.

Исходная статья обсуждает несколько вариантов. В одном варианте имитационной игры судья по текстовому каналу различает скрытых участников; затем место одного участника занимает машина. Современная короткая формула «человек и машина отвечают, судья угадывает» передаёт операционную идею, но не должна выдаваться за единственный неизменный регламент Тьюринга.

Почему текстовый канал? Он убирает голос, внешность и скорость почерка, чтобы судья работал с ответами. Почему разрешены свободные вопросы? Тьюринг хотел избежать узкого экзамена по одной способности. Цена свободы высока: результат сильно зависит от судьи, тем, длительности и правил игры.

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

Поведенческий критерий требует протокола

Один разговор оставляет слишком много свободы для объяснений задним числом. Эксперимент начинается до первого ответа. Нужно заранее зафиксировать:

1. совокупность источников, например конкретную версию модели и группу людей;
2. банк вопросов и правило выбора;
3. число диалогов от каждого источника;
4. канал, длину ответа и доступные инструменты;
5. случайный порядок с опубликованным seed;
6. момент фиксации решения судьи;
7. основную метрику и правило работы с пропусками.

Если вопросы выбирают после просмотра ответов, исследователь способен неосознанно подобрать удобные примеры. Если метку источника видно в длине файла или пунктуации, судья решает побочную задачу. Если один человек написал все человеческие ответы, результат не переносится на людей вообще.

Рис. 4.5 задаёт воспроизводимый пятишаговый протокол. В нижней части приведён полностью синтетический пример отчёта: 40 диалогов, по 20 каждого источника, и матрица решений. Числа не описывают реальную модель. Они нужны, чтобы проверить формулы.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Матрица решений показывает, где ошибся судья

Пусть строки матрицы задают скрытый источник, а столбцы решение судьи:

$$C= \begin{pmatrix} 14&6\\ 8&12 \end{pmatrix}.$$

В первой строке лежат 20 машинных ответов: 14 распознаны как машинные, 6 приняты за человеческие. Во второй строке 20 человеческих ответов: 8 названы машинными, 12 человеческими. Общая точность равна

$$\widehat p=\frac{14+12}{40}=0{,}65.$$

При сбалансированных источниках случайное угадывание даёт $0{,}5$. Но одна точность скрывает направление ошибок. Доля распознанных машинных ответов равна

$$\operatorname{TPR}_{M}=\frac{14}{14+6}=0{,}70,$$

а доля правильно распознанных человеческих ответов

$$\operatorname{TPR}_{H}=\frac{12}{8+12}=0{,}60.$$

Судья чаще принимает человека за машину, чем машину за человека. При несбалансированном наборе общая точность могла бы стать высокой за счёт частого класса, поэтому полезно считать сбалансированную точность:

$$\operatorname{BA}= \frac{\operatorname{TPR}_{M}+\operatorname{TPR}_{H}}{2}=0{,}65.$$

Одна доля ещё не знает своей точности

Наблюдаемая доля $\widehat p=k/n$ меняется от выборки к выборке. Для небольшого $n$ симметричный интервал $\widehat p\pm1{,}96\sqrt{\widehat p(1-\widehat p)/n}$ ведёт себя плохо у нулей и единиц и может выйти за $[0,1]$. Интервал Уилсона остаётся внутри допустимых границ.

При $z=1{,}96$ его центр и полуширина равны

$$c_W= \frac{\widehat p+\frac{z^2}{2n}}{1+\frac{z^2}{n}},$$ $$h_W= \frac{z}{1+\frac{z^2}{n}} \sqrt{ \frac{\widehat p(1-\widehat p)}{n} +\frac{z^2}{4n^2} }.$$

Интервал записывается как

$$I_W=[c_W-h_W,\ c_W+h_W].$$

Для $k=26$, $n=40$ получаем $\widehat p=0{,}65$ и $I_W\approx[0{,}495;0{,}779]$. Нижняя граница едва ниже $0{,}5$. Такой опыт не даёт уверенного основания утверждать, что судья различает источники лучше случайности на заявленной совокупности.

Обратная ошибка тоже опасна. Если судья угадал 20 из 40, нельзя объявлять источники неразличимыми. Для $\widehat p=0{,}5$ интервал широк: примерно $[0{,}352;0{,}648]$. «Не нашли отличие» и «доказали близость» имеют разный смысл. Для утверждения о практической неразличимости заранее выбирают допуск $\Delta$, например $0{,}10$, и требуют, чтобы весь доверительный интервал лежал внутри

$$[0{,}5-\Delta,\ 0{,}5+\Delta].$$

Сорока наблюдений для такого строгого вывода обычно мало.

Слепая лаборатория показывает механику, не рейтинг моделей

Лаборатория содержит 20 редакционных ответов: 10 помечены как «условная машина», 10 как «условный человек». Это синтетическая конструкция для обучения. Реплики не собраны у реальных людей и моделей, поэтому итог нельзя цитировать как исследование их способностей. Случайным остаётся только порядок; начальный seed = 1950 позволяет его повторить.

Сначала зафиксируйте решение «Человек» или «Машина». Только после выбора открываются источник, фактологическая оценка и пояснение. На правой половине обновляются матрица и интервал. Пройдите хотя бы десять раундов без возврата. Перед каждым ответом запишите один признак, которым вы пользуетесь: точность, оговорка, юмор, формальность или признание нехватки данных. После раскрытия проверьте, какой признак действительно предсказывал редакционную метку.

Кнопка «Новый порядок» увеличивает seed на единицу и перемешивает те же записи. Она не создаёт новую выборку ответов. Поэтому второй проход знакомого человека уже загрязнён памятью. Для честного сравнения судей каждому нужен один проход, а ответы следует собирать независимо.

Несколько судей создают второй уровень данных

Пусть один и тот же набор оценивают $m$ судей. Простого среднего accuracy мало: судьи могут использовать общую неверную подсказку. Сначала полезно измерить их согласие. Для двух судей с долями решений по категориям $a_M,a_H$ и $b_M,b_H$ ожидаемое случайное согласие равно

$$p_e=a_Mb_M+a_Hb_H.$$

Если фактическая доля одинаковых решений равна $p_o$, коэффициент Коэна

$$\kappa=\frac{p_o-p_e}{1-p_e}$$

вычитает согласие, ожидаемое из частот категорий. Значение $\kappa=1$ означает полное совпадение решений двух судей; оно не доказывает правильность. Оба способны одинаково читать скрытый водяной знак или разделять общий предрассудок.

Истинная метка источника позволяет отдельно считать accuracy каждого судьи. Если метка спорна, например ответ отредактирован человеком после генерации, задача уже не бинарна. Протокол должен заранее определить класс гибридов или исключить их, сохранив журнал исключений.

В уроке 03 коэффициент $\kappa$ сравнивал разметчиков. Здесь объект другой, но формула сохраняется. Backlink содержателен: одна и та же статистическая идея проверяет качество человеческого измерительного прибора.

Человеческий стиль и истинность расходятся

Ответ имеет несколько координат. Для школьного ассистента можно отдельно оценить фактическую точность $F$, сходство с человеческим стилем $S$ и качество объяснения $E$. Каждая координата лежит, например, на шкале от 0 до 5:

$$r=(F,S,E)\in[0,5]^3.$$

Сведение к одному баллу

$$R=w_FF+w_SS+w_EE$$

требует весов. Если $w_S$ велик, красноречивая ошибка обгонит сухой правильный ответ. Если $w_F=1$, а остальные веса нулевые, мы перестанем измерять имитацию и получим обычный экзамен на точность. Ни один выбор не нейтрален.

Рис. 4.6 показывает синтетические редакционные оценки. Форма маркера кодирует условный источник, координаты задают точность и стиль, цвет показывает объяснение. На графике есть точный, но нарочито машинный ответ; есть уверенная человеческая ошибка. Их существование разрушает попытку заменить одну ось другой.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Имитационная игра отвечает на операционный вопрос: может ли выбранная группа судей различить источники в выбранном канале при выбранных заданиях? Это ценный вопрос, если протокол построен под цель проверки. Для школьного помощника, медицинской подсказки и генератора шуток цели различны.

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

В уроке 32 мы разделим настройку и окончательный тест. Для имитационной игры это особенно важно: многократный просмотр банка вопросов превращает тест в обучение. В уроке 73 появится механизм предсказания следующего токена. Он объяснит часть внутренней процедуры языковой модели, но сам по себе не предскажет результат каждой поведенческой проверки.

Карта обещаний

Теперь можно положить рядом четыре утверждения.

Объект	Обещание	Что считается успехом	Что не следует из успеха
машина инкремента	завершиться на всякой конечной двоичной строке	инвариант, результат $N+1$, граница $2n+2$	быстрота любой другой программы
распознаватель остановки	подтвердить каждый случай $P(x)\downarrow$	конечная трасса остановившегося запуска	ответ «не остановится» после конечного ожидания
экспоненциальный перебор	проверить $2^n$ вариантов	последний вариант достигнут за конечное время	практическая доступность при большом $n$
слепой судья	различать источники в заданном протоколе	матрица решений и интервал для выбранной совокупности	сознание, истинность или внутренний механизм

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

Что осталось на ленте

Мы начали с числа 1011₂ и получили 1100₂ за восемь проверяемых переходов. Для произвольного входа доказали остановку через две убывающие меры и вывели точное время $T(n,r)=n+r+2$.

Затем программа стала данными. Это позволило сформулировать тотальный анализатор $H(P,x)$ и подать диагональной программе собственный код. Два возможных ответа $H(d,d)$ привели к противоречию. Доказательство запрещает общий безошибочный решатель, но сохраняет частичные анализаторы, ограниченные языки и честный ответ «не знаю».

Мы отделили неразрешимость от экспоненциального времени. У перебора $2^n$ есть последняя операция; у задачи остановки нет тотального алгоритма. Распознаваемость заняла промежуточное место: остановку можно подтвердить конечной трассой, а общий случай неостановки нельзя распознать симметрично.

Наконец, имитационная игра превратилась из разговора в опыт. Банк вопросов, случайный порядок, слепое решение, матрица ошибок и интервал Уилсона ограничили вывод. Человеческий стиль, фактическая точность и качество объяснения остались разными координатами.

Главный инструмент урока прост: выписывать обещание с кванторами и протоколом. Тогда становится видно, где нужна трасса, где доказательство, где оценка ресурса, а где доверительный интервал.

Задачи