Предсказуемость: какой вопрос на самом деле решает ИИ

Фрагмент лекции: «Все что нужно знать про ИИ айтишнику», 00:00 — отсюда взято содержание этой главы.

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

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

Что вообще называют искусственным интеллектом

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

В этой формулировке нагрузку несут два слова, и оба не про то, о чём обычно спорят.

«Имитировало» — про наблюдаемое поведение, а не про внутреннее устройство. Определение ничего не говорит о том, происходит ли внутри что-то похожее на мышление. Оно говорит только про то, как система выглядит снаружи.

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

Это отрезвляющая рамка, и она полезна ровно тем, что снимает половину споров: «является ли X искусственным интеллектом» — вопрос про происхождение X, а не про его уровень. Спор о том, думает ли модель, — отдельный, и он разбирается в главе «Могут ли нейросети думать».

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

Линия, по которой к этому шли

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

Аристотель первым описал вывод как набор форм: силлогистика задаёт правила, по которым из двух посылок получается заключение, независимо от содержания посылок (SEP, Aristotle’s Logic). Это ключевой ход — «правильность» перестаёт зависеть от того, о чём именно идёт речь.

Дальше логику превратили в исчисление: алгебра высказываний Буля, кванторы и строгий синтаксис Фреге, программа Гильберта по полной формализации математики. Параллельно теория множеств Кантора дала общий язык для всей математики — и вместе с ним парадоксы, кризис оснований и вопрос, который оказался решающим: существует ли механическая процедура, которая для любого утверждения формальной системы определяет, выводимо оно или нет (Entscheidungsproblem).

Чтобы ответить «нет», сначала пришлось строго определить, что такое «механическая процедура». Именно из этой необходимости родилось понятие алгоритма — и вместе с ним компьютер.

Отдельно про научный метод, потому что в лекции этот сюжет проговорён неточно. Там прозвучало, что науку «закрепил» Гегель триадой тезис — антитезис — синтез. Поправка нужна дважды. Во-первых, триада в таком виде Гегелю не принадлежит: её сформулировал Генрих Мориц Халибеус, отталкиваясь от Фихте, и приписывание её Гегелю — устойчивая историческая ошибка (SEP, Hegel’s Dialectics). Во-вторых, научный метод к диалектической триаде не сводится вообще. Линия, о которой на самом деле идёт речь, другая: эмпирический метод — наблюдение, эксперимент, индуктивный вывод — восходит к Фрэнсису Бэкону и его «Новому Органону» (1620), а критерий, отделяющий научное утверждение от ненаучного, — фальсифицируемость Карла Поппера (SEP, Scientific Method, SEP, Karl Popper).

Важно, что происходит на последнем шаге. Формализация логики закончилась не всемогущей машиной, а строгой границей: есть задачи, которые не решает никакой алгоритм. И одновременно — точным определением того, что алгоритм всё-таки может.

Две модели вычисления, и обе строго детерминированные

В 1936 году ответ на Entscheidungsproblem дали независимо и двумя разными способами.

Машина Тьюринга

Алан Тьюринг в работе «On Computable Numbers, with an Application to the Entscheidungsproblem» описал предельно простое устройство:

• лента — бесконечная последовательность ячеек, в каждой один символ из конечного алфавита;
• головка — смотрит ровно на одну ячейку, умеет прочитать символ, записать символ и сдвинуться на одну позицию;
• конечное множество состояний — вся «память» устройства, кроме ленты;
• таблица переходов — правило вида «в состоянии q при символе s запиши s', сдвинься влево или вправо, перейди в состояние q'».

Вот и всё устройство. Ниже — машина, прибавляющая единицу к двоичному числу на ленте.

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

Лямбда-исчисление

Алонзо Чёрч подошёл с другой стороны: никакой ленты, никакого состояния, только выражения и одно правило преобразования. Всё строится из трёх конструкций — переменная, абстракция λx. M, применение M N, — а вычисление есть подстановка (бета-редукция).

ID     = λx. x                  тождество
TRUE   = λx. λy. x              выбирает первый аргумент
FALSE  = λx. λy. y              выбирает второй аргумент
IF     = λc. λt. λe. c t e      условный оператор через выбор

IF TRUE A B  →  TRUE A B  →  (λx. λy. x) A B  →  A

Ни чисел, ни ветвлений, ни памяти в языке нет — всё это выражается функциями. И этого достаточно, чтобы выразить любое вычисление. Теорема Чёрча — Россера добавляет к картине важную деталь: если у выражения есть нормальная форма, она единственна и не зависит от порядка редукции. То есть детерминирован даже результат, а не только процесс.

Тезис Чёрча — Тьюринга

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

Из этого совпадения родился тезис Чёрча — Тьюринга: то, что мы интуитивно называем «эффективно вычислимым», совпадает с тем, что вычисляет машина Тьюринга. Формально это не теорема, а именно тезис — утверждение о совпадении неформального понятия со строгим, поэтому доказать его нельзя, а опровергнуть можно было бы контрпримером (SEP, The Church—Turing Thesis).

Практический смысл всей этой конструкции для нас один. Реальный компьютер — инженерное воплощение детерминированной модели. Процессор исполняет инструкцию как функцию от своего состояния. Никакого места, где в эту схему могла бы просочиться случайность, в модели нет.

Дыра: детерминированная машина не производит случайность

Теперь очевидное следствие, которое почему-то почти никогда не проговаривают вслух.

Когда вы пишете random.randint(1, 100), вы вызываете обычную функцию. Внутри неё — переменная состояния s и две чистые функции: s_next = f(s) вычисляет следующее состояние, output = g(s) превращает состояние в число. Никакой физики, никакого контакта с внешним миром. Значит, одинаковое s даёт одинаковую последовательность до конца времён.

Это не недоработка библиотеки и не лень авторов стандарта. Это прямое следствие того, что машина вычисляет функции. Поэтому такие генераторы честно называются псевдослучайными — PRNG, pseudo-random number generator. Начальное состояние называется seed.

import random

# --- 1. PRNG полностью определяется seed ---
random.seed(42)
first = [random.randint(1, 100) for _ in range(5)]

random.seed(42)                     # тот же seed — тот же старт
second = [random.randint(1, 100) for _ in range(5)]

print(first)                        # [82, 15, 4, 95, 36]
print(second)                       # [82, 15, 4, 95, 36]
print(first == second)              # True

# --- 2. Состояние можно снять и вернуть: генератор — это просто данные ---
state = random.getstate()           # снимок внутреннего состояния
a = random.random()                 # 0.24489185380347622
random.setstate(state)              # откатываем генератор назад
b = random.random()                 # 0.24489185380347622
assert a == b                       # «случайность» воспроизводится точно

# --- 3. Независимые генераторы с одним seed идут синхронно ---
g1, g2 = random.Random(2026), random.Random(2026)
assert [g1.random() for _ in range(3)] == [g2.random() for _ in range(3)]

Стандартный модуль random в CPython использует Mersenne Twister MT19937 (документация). Его свойства хорошо характеризуют весь класс:

• период 2**19937 - 1 — последовательность не повторится за любое разумное время;
• состояние — 624 32-битных слова, то есть примерно 2,5 КБ; сложность генерации одного числа — O(1) по времени и O(1) по памяти;
• распределение отличное: результаты проходят статистические тесты на равномерность;
• предсказуемость полная: наблюдая достаточное число выходов, внутреннее состояние восстанавливается, и весь дальнейший поток вычисляется точно.

Последний пункт — не теоретическая придирка, а источник реальных уязвимостей. Достаточно, чтобы seed угадывался: классическая ошибка — засеять генератор текущим временем и выдавать из него токены.

import random, time, string

def weak_token() -> str:
    """Так делать нельзя: seed берётся из времени, а оно известно атакующему."""
    rnd = random.Random(int(time.time()))
    return "".join(rnd.choice(string.hexdigits[:16]) for _ in range(16))

def crack(token: str, now: int, window: int = 300) -> int | None:
    """Перебираем секунды за последние 5 минут — 300 вариантов, доли секунды работы."""
    for candidate in range(now - window, now + 1):
        rnd = random.Random(candidate)
        guess = "".join(rnd.choice(string.hexdigits[:16]) for _ in range(16))
        if guess == token:
            return candidate           # seed восстановлен, дальше предсказуем весь поток
    return None

token = weak_token()
print(crack(token, int(time.time())))  # печатает seed, а не None

Пространство seed здесь — не 2**19937, а число секунд в окне поиска. Требования к случайности в контексте безопасности разобраны в RFC 4086 «Randomness Requirements for Security» — документ целиком про то, что арифметика не заменяет физику.

Откуда компьютер всё-таки берёт непредсказуемость

Раз внутри модели вычислений случайности нет, её приходится ввозить снаружи — из физических процессов, которые в модель не входят. Такие источники называют источниками энтропии.

Здесь стоит поправить лекцию: сервис random.org не «сканирует состояние химических элементов в литосфере» — он использует атмосферный шум, снимаемый радиоприёмниками, и публикует методику вместе с результатами статистического анализа (описание источника, анализ).

Операционная система собирает такие события в пул, перемешивает их криптографической функцией и раздаёт приложениям через криптостойкий генератор (CSPRNG). Вот полный путь одного вызова:

Три практических факта, которые полезно знать точно:

1. /dev/random и /dev/urandom в современном Linux дают одинаковое качество после инициализации пула. Легенда о том, что первый «настоящий», а второй «поддельный», устарела: блокирующее поведение осталось только на этапе ранней загрузки (man random(4)).
2. Правильный системный вызов — getrandom(2), а не чтение файла устройства: он не тратит файловый дескриптор и корректно ведёт себя при неинициализированном пуле (man getrandom(2)).
3. RDRAND не используют напрямую. Аппаратный источник подмешивается в пул наравне с остальными — это защита от единственной точки доверия. Требования к таким конструкциям описаны в NIST SP 800-90A Rev. 1.

В прикладном коде вся эта механика скрыта за двумя вызовами:

import os, secrets

raw = os.urandom(16)                # 16 байт напрямую из системного CSPRNG
token = secrets.token_hex(16)       # тот же источник, удобная обёртка
pin = secrets.randbelow(1_000_000)  # без смещения, в отличие от % 1000000

# Ни seed, ни setstate у этих функций нет и быть не может:
# состояние живёт в ядре и подпитывается физическими событиями.

Модуль secrets появился в Python 3.6 ровно затем, чтобы разорвать привычку брать random для паролей и токенов. Разделение простое и запоминается одним правилом.

Типичные ошибки, которые встречаются чаще всего:

• Seed из времени. Показан выше: пространство перебора схлопывается до секунд.
• Общий генератор после fork или в multiprocessing. Дочерние процессы наследуют состояние и выдают одинаковые «случайные» последовательности. Лечится явной переинициализацией в каждом воркере — в NumPy для этого есть SeedSequence.spawn() (документация).
• Самодельное «усиление» случайности. Смешивание нескольких PRNG, добавление PID и времени, хеширование результата — всё это чаще ухудшает свойства, чем улучшает; RFC 4086 разбирает такие конструкции отдельно.
• Незаписанный seed в эксперименте. Прогон, который нельзя повторить, не является измерением. Эта дисциплина подробнее разобрана в оценке моделей.

Зачем эта дыра понадобилась искусственному интеллекту

Теперь соберём главу.

Формальная логика и вычислимость решают задачи, где ответ выводится из правил. Задан набор аксиом и правил вывода — заключение либо получается, либо нет. Это огромный класс задач, и на нём стоит вся классическая информатика.

Но есть другой класс, где правило выписать невозможно. Какое слово будет следующим в предложении. Что изображено на фотографии. Какой ход в этой позиции лучше. Здесь нет аксиом, из которых ответ выводится, — есть только наблюдения и частоты. Попытки решать такие задачи жёсткими правилами («если пиксели вот такие, то это кошка») упирались в комбинаторный взрыв и разбивались о первый же нестандартный пример; это была основная причина, по которой символьный ИИ 1970–1980-х не дал ожидаемого результата.

Найденное решение изящно и стоит того, чтобы сформулировать его точно: из машины детерминизм не убирали — вероятность внесли в описание задачи.

Всё, что слева и сверху, — обычный детерминированный счёт. Модель по входу считает распределение: не «ответ», а числа, показывающие, насколько правдоподобен каждый из вариантов. Эта часть воспроизводима до последнего бита.

Случайность нужна ровно в одной точке — когда из распределения надо выбрать один вариант. И берётся она у обычного PRNG с обычным seed. Отсюда два наблюдения, которые иначе выглядят загадочно:

• Один и тот же промпт даёт разные ответы — потому что сэмплирование каждый раз стартует с другого состояния генератора.
• Генерацию изображения можно воспроизвести по seed — потому что весь остальной путь строго детерминирован. Это подробно разбирается в главе про диффузионные модели.

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

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

Источники

• Turing, On Computable Numbers, with an Application to the Entscheidungsproblem (1936) — исходная работа с описанием машины
• SEP, The Church—Turing Thesis — что именно утверждает тезис и чего не утверждает
• SEP, Aristotle’s Logic и SEP, Hegel’s Dialectics — в том числе о происхождении триады «тезис — антитезис — синтез»
• SEP, Scientific Method и SEP, Karl Popper — эмпирический метод и фальсифицируемость
• RFC 4086, Randomness Requirements for Security — почему арифметика не заменяет физику
• NIST SP 800-90A Rev. 1 — требования к детерминированным генераторам в криптографии
• Документация Python: random, secrets, NumPy Random Generator
• man-страницы Linux: random(4), getrandom(2)
• random.org: об источнике случайности и статистический анализ выдаваемых чисел

Мини-итог

• «Искусственный интеллект» — термин о происхождении, а не об уровне: он описывает алгоритмизацию поведения, имитирующего размышление, и формально покрывает даже симуляцию муравья.
• Компьютер — воплощение детерминированной модели вычислений: машина Тьюринга и лямбда-исчисление Чёрча эквивалентны по силе и обе задают шаг однозначно.
• Тезис Чёрча — Тьюринга не теорема, а утверждение о совпадении интуитивного понятия «эффективно вычислимо» со строгим; опровергнуть его можно, доказать — нет.
• Из детерминизма прямо следует, что случайность внутри модели невозможна: random — это функция состояния, а seed полностью задаёт весь поток чисел.
• Настоящая непредсказуемость ввозится извне модели: тайминги прерываний, джиттер, аппаратные ГСЧ, атмосферный шум у random.org. В прикладном коде это secrets и os.urandom, а не random.
• Правило разделения простое: воспроизводимость нужна — PRNG с записанным seed; секретность нужна — системный CSPRNG.
• Вероятность внесли не в машину, а в модель: детерминированный счёт выдаёт распределение, и случайность нужна ровно в одной точке — при выборе варианта из него. Так появились стохастические модели.

Что дальше

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

Цепи Маркова: предсказание без понимания