Глава 2. Конечная память и лестница Хомского

Память как мера расстояния до пола

Глава 15.1 провела центральный разрез вычисления: ограниченная остановка разрешима (Element-сторона), безграничная — role-limit. Но между разрешимым полом и неразрешимым верхом нет голой стены: пространство между ними градуировано, и параметр градуировки — память.

Наша система читает это так:

сколько памяти вправе занять вычисление — это и есть мера того, как далеко оно стоит от Element-пола.

Фиксированная конечная память — сам пол: всё, что распознаётся ею, разрешимо. Каждый добавленный ресурс памяти — стек, ограниченная лента, неограниченная лента — ступень вверх, к role-limit-верху (halting, 15.3). Эта глава кладёт пол (конечный автомат), находит его потолок (стена-голубятня), делает один шаг вверх конкретно (язык $a^n{b}^n$ и порождающая его грамматика) и затем прочитывает всю иерархию Хомского как один градиент Element / role-limit, размеченный памятью — формализуя нижнюю ступень и читая всю лестницу как градиент.

Конечный автомат — Element-пол

Конечный автомат есть конечное множество состояний $Q$, переход $\delta :Q\times \Sigma \to Q$, предикат принятия и стартовое состояние. Распознавание слова $w$ — это прочесть его символы по одному, ведя состояние по $\delta$. Решающее здесь — слово конечное: состояний конечно, и это фиксированная конечная память; прогон завершается за $|w|$ шагов; вопрос «принимает ли автомат $w$?» разрешим — прогнать и прочитать бит принятия.¹

Это и есть Element-пол вычисления: конечно-актуальное, терминирующее, разрешимое, 0-аксиомное. Язык регулярен, когда его распознаёт какой-нибудь конечный автомат — то есть когда конечной памяти достаточно. Пол ведёт себя как добротный Element-класс: регулярные языки замкнуты относительно дополнения, пересечения и объединения (последние два — прямым произведением автоматов, где память есть пара состояний). Никакой тени неразрешимости: вся трудность придёт ровно тогда, когда конечной памяти перестанет хватать.

Лемма о накачке: стена конечной памяти

У пола есть потолок, и причина его — чистая голубятня. Пусть у автомата ровно $k$ состояний. Прогоним достаточно длинное слово: среди не менее чем $k+1$ посещённых состояний два обязаны совпасть — какое-то состояние посещается дважды. Между двумя визитами автомат прошёл петлю, вернувшую его в то же состояние; а петлю можно повторить («накачать») сколько угодно раз, и автомат всякий раз окажется в том же конечном состоянии — значит, накачанные слова все вместе либо принимаются, либо отвергаются.²

Читается это прямо: конечная память не умеет считать без границы — она вынуждена зацикливаться. Свойство накачки не трюк, а подпись ограниченной памяти (голубятня по состояниям). И оно размечает край пола: всякий язык, требующий различать неограниченно много «счётов», лежит за этим краем.

Язык $a^n{b}^n$ за стеной; первый шаг вверх — стек

Свидетель за стеной — язык $\{a^n{b}^n\}$: $n$ букв $a$, затем $n$ букв $b$. Чтобы его принять, машина обязана проверить, что число $b$ равно числу $a$, то есть сосчитать $n$ — а $n$ не ограничено. Конечной памяти не хватит. Доказывается это безусловно, без всякой «длины накачки»: для любого автомата с любым конечным $Q$ прогоним префиксы $a^0,a^1,a^2,\dots$; по голубятне два разных префикса $a^i,a^j$ ($i\ne j$) приводят в одно и то же состояние — и тогда автомат не различает $a^i{b}^i\in L$ и $a^j{b}^i\notin L$:

$$\begin{array}{c}\exists i\ne j:{\delta }^{\ast }(q_0,a^i)={\delta }^{\ast }(q_0,a^j)\\ ⟹\text{после дописывания }{b}^i\text{ вердикт один}—\text{принят неверный язык.}\end{array}$$

Поэтому ни один конечный автомат не распознаёт $\{a^n{b}^n\}$.³ Здесь ${\delta }^{\ast }$ — расширенный переход (прогон по слову).

Важна относительность: $\{a^n{b}^n\}$ есть role-limit по отношению к конечной памяти, а не абсолютно. Добавим один ресурс — стек (память «последним вошёл — первым вышел») — и считать уже можно: класть метку на каждом $a$, снимать на каждом $b$, принять, если стек опустел ровно. И действительно, $\{a^n{b}^n\}$ контекстно-свободен — он порождается грамматикой

$$S\to \epsilon |aSb.$$

В нашей системе эта грамматика записана как индуктивный предикат и проверена в обе стороны: она порождает ровно $\{a^n{b}^n\}$.⁴

Так делается доказанная ступень: $\text{регулярные}⊊\text{контекстно-свободные}$. Язык $\{a^n{b}^n\}$ лежит в верхнем классе (его порождает контекстно-свободная грамматика), но доказуемо не в нижнем (DFA нет) — настоящее строгое включение, проверенное машинно (0 аксиом). Характеризация контекстно-свободных через магазинный автомат — стандартное чтение, отдельно не формализованное.

Лестница Хомского как градиент Element / role-limit

Сложив ступени, получаем лестницу, где каждая ступень добавляет память:

Класс	Память	Место в градиенте
регулярные	конечное управление	Element-пол: членство разрешимо
$⊊$ контекстно-свободные	$+$ стек	доказанная ступень (через $a^n{b}^n$)
$⊊$ контекстно-зависимые	$+$ ограниченная лента	ярус выше (LBA; не формализован)
$⊊$ рекурсивно-перечислимые	полная лента	верх: членство сводится к остановке (полуразрешимо; 15.3)

В обычных учебниках иерархия Хомского — таксономия форматов грамматик. В нашей системе она один градуированный градиент Element / role-limit, и параметр градуировки — память. Низ — разрешимый Element-пол; верх — halting role-limit; каждая ступень добавляет ресурс памяти и поднимается по градиенту. «Насколько неразрешимо для данного класса памяти» $=$«как далеко над полом». Иерархия оказывается тонкой структурой центрального разреза 15.1: между «ограниченно-разрешимо» и «безгранично-role-limit» лежит не стена, а градуированная лестница.

Честная граница яруса. Машинно проверён нижний ярус (0 аксиом): разрешимость пола (membership_decidable), его замкнутость, стена-голубятня, DFA-нерегулярность $a^n{b}^n$ и первая строгая ступень $\text{регулярные}⊊\text{контекстно-свободные}$. Остальная лестница (контекстно-свободные$⊊$контекстно-зависимые$⊊$рекурсивно-перечислимые), эквивалентность Клини (регулярные выражения$\leftrightarrow$DFA) и характеризация контекстно-свободных магазинным автоматом — стандартное математическое чтение, отдельно не формализованы; неразрешимость верха (RE$=$halting) — это диагональ 15.3.

Разбор E/R/R: лестница как градиент ролей

Правила (L5). Упорядоченный переход $\delta$ (шаг автомата) и правила порождения грамматики ($S\to \epsilon \mid aSb$) конституируют язык; стена-голубятня — производное правило, размечающее край пола.

Роли (L4). Память есть роль: конечное управление, стек, ограниченная лента, полная лента — ресурсы-роли, которые вычисление вправе нести. А класс языка (регулярный, контекстно-свободный, …) — роль-ярус иерархии: место, которое язык занимает в градиенте.

{

Элементы (L1$+$P4). Конкретные слова, индуктивная грамматика CFG_anbn, конкретные автоматы, конечные прогоны. Не элемент: конечный автомат для $\{a^n{b}^n\}$ — он реифицировал бы неограниченный счёт в фиксированную память (голубятня запрещает).}

Компонент	Что фиксирует	E/R/R-категория
переход $\delta$; правила грамматики $S\to \epsilon \mid aSb$; стена-голубятня	конституцию и край языка	Правило (L5)
память (управление / стек / лента); класс языка как ярус	ресурс и место в градиенте	Роль (L4)
слова; грамматика CFG_anbn; автоматы; прогоны	конечно-актуальные носители	Элемент (L1$+$P4)

Диагностика P4. Лестница есть градиент role-limit’ов: «чего ступень не может» есть role-limit относительно её памяти; пол — Element (разрешим); подъём — добавление памяти — приближение к абсолютному role-limit (halting). В частности, $a^n{b}^n$ — не абсолютный role-limit, а role-limit относительно конечной памяти: добавь стек — и он становится Element следующего яруса (отсюда осторожность: нерегулярное $\ne$ невычислимое). Требовать от конечной памяти распознать $a^n{b}^n$ — значит реифицировать role-limit в Element-пол: смешение уровней, которое запрещает голубятня.

Что глава подготовила

Пол положен (конечная память — разрешимое членство), потолок найден (голубятня / накачка), первая ступень пройдена конкретно ($a^n{b}^n$ порождается грамматикой $S\to \epsilon \mid aSb$, но не распознаётся никаким DFA — значит $\text{регулярные}⊊\text{контекстно-свободные}$), и вся иерархия Хомского прочитана как один градиент Element / role-limit, размеченный памятью. Весь доказанный слой главы 0-аксиомен и машинно проверен: DFA / NFA, регулярный Element-пол, накачка / голубятня, нерегулярность $a^n{b}^n$ и первая строгая ступень. Верхние ярусы названы честно как стандартное чтение, а не выданы за проверенное.

Самый верх лестницы — членство в рекурсивно-перечислимом языке — полуразрешимо и сводится к остановке ($\mathrm{halts}$): это ровно тот role-limit, чей двигатель — диагональ неподвижной точки. Глава 15.3 открывает этот двигатель: одна диагональ, ведущая halting, Райса, Кантора и Колмогорова.

---

---

Часть: Часть XV. Вычисления и граница финитизации · Том: «Математика»

Навигация: ← Глава 1. Вычисление как финитизация · Глава 3. Одна диагональ: halting, Райс, Кантор, Колмогоров →

Footnotes

1. Механика конечных автоматов — src/stdlib/Automata.v (DFA/NFA). Element-пол — src/cs/RegularElementFloor.v (9 Qed, 0 аксиом): run (прогон автомата по слову), accepts (принятие), membership_decidable (разрешимость членства), complement_spec; замкнутость по пересечению и объединению — через произведение автоматов (dprod, run_prod, intersection_spec, union_spec). ↩

2. src/cs/PumpingRoleLimit.v (11 Qed, 0 аксиом): повторно посещённое состояние есть петля (loop_pump), накачка сохраняет конечное состояние (pump_preserves); язык $a^n{b}^n$ — word_a, word_b, In_L; счётчики букв cF/cT и баланс anbn_balanced (если $a^j{b}^i\in L$, то $i=j$). ↩

3. Безусловное отсутствие DFA — src/cs/PumpingPigeonhole.v (4 Qed, 0 аксиом): голубятня на состояниях-префиксах (gpref, gpref_collision) даёт no_dfa_for_ anbn_ unconditional. ↩

4. src/cs/ChomskyHierarchy.v (8 Qed, 0 аксиом): CFG_anbn (правила $S\to \epsilon \mid aSb$), CFG_anbn_iff_In_L (грамматика порождает РОВНО $a^n{b}^n$), regular_recognized (формально: «некоторый DFA распознаёт»), regular_ subsetneq_ context_free (строгое включение). ↩