Глава 1. Вычисление как финитизация

Где стоит часть и глава

После метатеоретического поворота Части XIV, где категория оказалась языком ToS, том переходит к прикладной математике. Часть XV утверждает простое и сильное:

вычисление есть граница финитизации, ставшая алгоритмической.

Та самая граница, что делила рациональное и иррациональное (Часть IV), конструктивное и классическое, дискретный и континуальный спектр, здесь принимает вычислительную форму: алгоритм над конечными данными либо завершается — и тогда он на Element-стороне, разрешим; либо не завершается — и тогда он role-limit, неразрешим или невычислим.

Эта глава кладёт основание: что есть вычисление в нашей системе и каков его центральный разрез — ограниченная остановка разрешима, а безграничная есть role-limit. Дальше часть развернёт две стороны этого разреза: неразрешимую (одна диагональ, 15.3) и разрешимую (один дискриминант, 15.4), между которыми лежит градуированная лестница языков (15.2).

Вычисление как процесс

Вычисление в ToS есть процесс с собственной триадой E/R/R. Его элементы — конфигурации (состояния машины). Его правило — упорядоченный шаг: именно ПОРЯДОК шагов (L5) превращает последовательность конфигураций в вычисление, а не в произвольный список. И его статус — остановка: достигнут ли результат (это статусный компонент, не роль — см.\ разбор §15.1.6).

Машина запускается не «до конца», а на конечную глубину $n$ — это и есть P4 («бесконечность есть свойство процесса, не объекта»):

$$\mathrm{run}0c=c,\mathrm{run}(n+1)c=\{\begin{array}{ll}\mathrm{run}nc,& \text{если }c\text{ уже остановлена на шаге }n,\\ \mathrm{step}(\mathrm{run}nc),& \text{иначе.}\end{array}$$

Раз достигнув результата, конфигурация становится неподвижной точкой дальнейшего бега (остановка поглощающая), а сам факт остановки монотонен по бюджету: появившись на шаге $n$, он держится при всех $m\ge n$.¹ Все эти факты конструктивны: ни классической логики, ни выбора они не требуют.

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

Element-сторона: ограниченная остановка разрешима

Зафиксируем бюджет $n$. Вопрос «остановилась ли конфигурация за $n$ шагов?» — это

$$\mathrm{halt}{\mathrm{s}}_{\mathrm{i}}\mathrm{n}nc:=(\mathrm{halted}(\mathrm{run}nc)=\text{true}),$$

и он разрешим: для любого фиксированного $n$ есть конструктивное булево решение — прогнать $n$ шагов и посмотреть статус. Это терминирующая процедура, и она 0-аксиомна. ³ Это Element-сторона вычисления: конечно-актуальное, вычислимое, наблюдаемое. Машина обратного отсчёта из $3$ останавливается в пределах бюджета — факт, проверяемый прямым вычислением.

Важно, почему ограниченная остановка разрешима: бюджет $n$ делает процесс конечным (P4). Решение не «угадывает будущее» — оно лишь читает результат конечного прогона. Здесь нет ни тени неразрешимости: вся трудность части возникнет ровно тогда, когда бюджет снимут.

Role-limit-сторона: безграничная остановка

Снимем бюджет. Полная остановка

$$\mathrm{halts}c:=\exists n,\mathrm{halt}{\mathrm{s}}_{\mathrm{i}}\mathrm{n}nc$$

есть завершение бега по всем бюджетам. Положительный случай сам по себе имеет конечного свидетеля (если машина остановилась за какое-то $n$ — тогда это Element); role-limit возникает как универсальная задача распознавания — решить этот предикат для всех конфигураций сразу (в частности отрицательно) требует контроля над всеми бюджетами одновременно. Двойственно, расходимость (\mathrm{diverges} c := \forall n,
\mathrm{halted} (\mathrm{run} n c)=\text{false}) — результат не достигается ни на какой конечной глубине; остановка и расходимость взаимоисключающи.

P4-диагностика. Безграничная остановка не есть Element-объект. Взять «останавливается ли вообще?» за разрешимый булев предикат — значит реифицировать role-limit в Element: категориальная ошибка того же рода, что «бесконечность как завершённый объект» (Часть IV). Честная формулировка не «мы не умеем вычислить», а «role-limit нельзя финитизировать в Element-решатель». Точную форму этого — отсутствие универсального решателя остановки — даёт диагональ (15.3); здесь мы лишь проводим разрез: ограниченное — Element, разрешимо; безграничное — role-limit. Машина-инкремент без статуса остановки даёт пример отрицательной стороны: каждый конечный прогон существует, но результата нет ни на одном бюджете — расходимость, чистый role-limit.

Граница финитизации, ставшая алгоритмической

Разрез «ограниченно-разрешимо / безгранично-role-limit» и есть граница финитизации проекта (Element / role-limit), теперь в вычислительной форме:

$$\begin{array}{c}\text{терминирует с конечным свидетелем (в фиксированном бюджете)}\\ ⟺\text{Element}⟺\text{разрешимо на конечной стадии}.\end{array}$$

Точность здесь существенна: безграничный предикат $\mathrm{halts}c:=\exists n,\mathrm{halt}{\mathrm{s}}_{\mathrm{i}}\mathrm{n}nc$ в конкретном случае может иметь конечного свидетеля $n$ (если машина и впрямь остановилась) — и тогда он Element; role-limit возникает в требовании тотального решателя этого предиката для всех программ — его и запретит диагональ (15.3). Это та же линия, что в Части IV делила рациональное (терминирующий процесс) и иррациональное (нетерминирующий), а в общем принципе — конструктивное и классическое. Вычисление лишь делает её алгоритмической: разрешимость становится свойством конкретной процедуры на конечной стадии.

У границы две стороны, и обе несёт одна арена. Неразрешимая сторона имеет один двигатель — диагональ (теорема о неподвижной точке), порождающую halting, Райс, Кантора и Колмогорова (15.3). Разрешимая сторона имеет один критерий — дискриминант редукционного атласа (15.4). Между ними лежит градуированная лестница языков (15.2). Всё это собирается в один машинный итог — «вычисление есть граница финитизации»: Element-разрешимость на любой машине, role-limit как одна диагональ, корень в теореме Лавера.⁴

Разбор E/R/R: вычисление как E/R/R

Правила (L5). Упорядоченный шаг (L5) делает последовательность конфигураций вычислением; run $n$ — развёртка на конечную глубину (P4); и сам разрез «терминирует $\iff$ Element» есть правило, конституирующее вычислимость.

Роли (L4). Остановка (halted) — это статус (чем конфигурация стала под правилами), а не роль (различение Status $\ne$ Role); решатель остановки — роль-оракул; безграничная остановка $\mathrm{halts}$ — роль-предел (завершение run по всем $n$).

{

Элементы (L1$+$P4). Конкретные конфигурации, fuel-ограниченные прогоны run $n$, машина обратного отсчёта. Не элемент: тотальный оракул остановки — его role-limit нельзя финитизировать в Element-решатель (P4 / диагональ запрещают).}

Компонент	Что фиксирует	E/R/R-категория
упорядоченный шаг + run $n$ + разрез «терминирует$\iff$Element»	конституцию вычислимости	Правило (L5)
статус-остановка; решатель-оракул; \mathrm{halts}$${}={}роль-предел	статус и пределы процесса	Роль (L4)
конфигурации; прогоны run $n$; countdown	конечно-актуальные носители	Элемент (L1$+$P4)

Диагностика P4. Ограниченная остановка (фиксированный бюджет) = Element: разрешима, булева, 0 аксиом. Безграничная = role-limit: «решить halting вообще» было бы смешением уровней. Граница не запрещает — она называет масштаб: что схватывается конечным прогоном, а что есть предел/процесс.

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

Вычисление предъявлено как процесс с триадой E/R/R: конфигурации (элементы), упорядоченный шаг (правило L5), статус-остановка (роль); run $n$ — развёртка на конечную глубину (P4), а конфигурация-арена связывает их в один объект. Проведён центральный разрез части: ограниченная остановка разрешима (Element, 0 аксиом), безграничная — role-limit; это и есть граница финитизации, ставшая алгоритмической. Всё опирается на 0-аксиомный машинно проверенный слой; честные стены (невычислимость, несчётность континуума) встанут на своих местах позже и соберутся в 15.7.

Дальше — Глава 15.2: конечная память и лестница Хомского, где Element-пол (регулярные языки) оказывается нижней ступенью градуированного градиента role-limit’ов, ведущего к самому верху — halting (15.3).

---

---

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

Навигация: ← Глава 7. Синтез: вся ToS как категория; мост к теории типов; карта границ — Часть XIV · Глава 2. Конечная память и лестница Хомского →

Footnotes

1. src/cs/HaltingRoleLimit.v (13 Qed, 0 Admitted, 0 аксиом): run, run_absorb (поглощение), halts_in_mono (монотонность по бюджету), halts_not_diverges (взаимоисключение остановки и расходимости). ↩

2. src/cs/ComputationModel.v (3 Qed, 0 аксиом): Record CompModel (конфигурации$+$шаг$+$статус), cm_halts_in, cm_halts; конкретный обитатель арены — машина обратного отсчёта (countdown). ↩

3. HaltingRoleLimit.v: bounded_halting_decidable — разрешимость $\{\mathrm{halt}{\mathrm{s}}_{\mathrm{i}}\mathrm{n}nc\}+\{\neg \mathrm{halt}{\mathrm{s}}_{\mathrm{i}}\mathrm{n}nc\}$; та же разрешимость на арене — ComputationModel.cm_ bounded_ decidable. ↩

4. ComputationModel.computation_ is_ finitization_ boundary: конъюнкция (1) ограниченная остановка разрешима на любой машине; (2) одна диагональ в четырёх гранях; (3) корень — lawvere_fixed_point. 0 аксиом. Здесь — как ориентационный синтез; подробное раскрытие в финале 15.7. ↩