Настоящая статья посвящена анализу научной и философско-методологической программы выдающегося математика современности, Научного руководителя Института фундаментальной математики Дмитрия Леонидовича Гуриновича (цикл работ 2017–2026 годов) в контексте развития идей Давида Гильберта и Курта Гёделя.

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

В центре внимания данного исследования находится перенос метаматематического подхода Гильберта и диагонального метода Гёделя в плоскость современной теории алгоритмов и вычислительной сложности. Последовательно прослеживаются два этапа эволюции взглядов Д.Л. Гуриновича:

1. Этап алгоритмической адаптации (2017 г.): перевод теорем о неполноте и неопределимости на язык классов сложности, введение понятия «авторизуемых задач» и математическая формализация свойства рефлексии, при котором алгоритм-решение анализирует собственный программный код.

2. Этап ревизии оснований вычислимости (2020–2025 гг.): критика выразительных возможностей абстрактной арифметики Пеано и построение альтернативного формального фундамента на базе практического опыта информационных технологий — типированной «арифметики строк», объектно-ориентированного расширения логики и архитектуры «Машины исполнения компьютерных алгоритмов, Русской машины Гуриновича» (МКА) с неограниченными лучами данных.

Цель предлагаемого обзора — дать систематическую, концептуально полную и источниковедчески выверенную реконструкцию открытий Д. Л. Гуриновича, отделив и связав прямое наследование классических методов школы Гильберта и радикальный пересмотр базовых инструментов математической логики и теории вычислимости.

Полный текст размещён выше.

Сокращённый по техническим причинам текст размещён ниже, также как и послесловие Научного Руководителя Института фундаментальной математики, ниже по тексту

Дмитрий Гуринович, научный руководитель Института фундаментальной математики, как наследник и продолжатель научных идей Гильберта и Гёделя

 

Исследовательская программа выдающегося российского математика и ИТ-специалиста современности Дмитрия Леонидовича Гуриновича, развернутая в цикле работ 2017–2026 годов,) представляет собой масштабную попытку прямого переноса, модернизации и критического переосмысления метаматематического проекта Давида Гильберта и теорем о неполноте Курта Гёделя применительно к фундаментальным проблемам теории алгоритмов, вычислительной сложности и оснований информатики.

Выступая идейным продолжателем гильбертовской теории доказательств (Beweistheorie) и гёделевского метода диагонализации, Дмитрий Леонидович Гуринович ставит перед современной математикой задачу, аналогичную той, которую Гильберт сформулировал в начале XX века для формальной логики: исследовать возможности и границы алгоритмического поиска доказательств формализованными средствами самой теории. На этом пути учёный переводит классические теоремы о логической неразрешимости и неполноте на язык классов вычислительной сложности, предлагая неклассическое доказательство неравенства  на основе формализации алгоритмической самореференции («рефлексии»), а затем переходит к радикальной ревизии базового инструментария эпохи Гильберта и Гёделя — замене унарной арифметики Пеано, гёделевой нумерации, частично рекурсивных функций и машины Тьюринга на типированную «арифметику строк», объектно-ориентированную логику и «Машину исполнения компьютерных алгоритмов (Русская машина Гуриновича)» (МКА).

Эволюция научных взглядов Дмитрия Леонидовича Гуриновича делится на два качественно различных этапа, отражающих диалектику наследования и преодоления классического фундаментализма.

На первом этапе (2017 год, работы «Программа Гильберта, , Рефлексия» и «Языки логики и классы сложности. Рефлексия. ») учёный действует внутри классической парадигмы: он опирается на аксиоматику Пеано, тезис Чёрча и правила вывода из выдающегося труда Д. Гильберта и П. Бернайса «Основания математики», модифицируя способ кодирования формул (переход от гёделевых номеров к символьным строкам) и вводя понятие «авторизуемых задач», где алгоритм проверки анализирует программный код самого алгоритма-решения.

На втором этапе (2020–2025 годы, цикл статей о теории строк, вычислимости по Тьюрингу, невычислимости чисел арифметики Пеано и ООП-расширении логики) Дмитрий Леонидович Гуринович приходит к выводу, что сам математический аппарат, созданный в эпоху Гильберта и Гёделя для решения качественных вопросов логики, то есть существование конечного вывода безотносительно его размера и времени поиска, является слишком «грубым» и недостаточно выразительным для количественных задач теории алгоритмов.

Развитие идей Гильберта в части требования полной формализации и финитной наглядности модели в результате приводит Д.Л. Гуриновича к отказу от абстрактной арифметики Пеано в пользу приоритета физической и компьютерной реальности вычислений.

Отметим, что все рассматриваемые труды Д.Л. Гуриновича представляют собой авторские препринты и монографии, депонированные в российском реестре ЕДРИД (edrid.ru). Сам автор является выпускником математического класса московской школы № 330, где он учился вместе с будущим лауреатом Филдсовской премии В. В. Воеводским, профессионально работает в Институте фундаментальной математики.

Сам Д.Л. Гуринович указывает, что его доказательство  на сегодняшний день построено для специального подкласса «авторизуемых» (рефлексивных) задач, тогда как для классических задач Кука с единым ограничивающим полиномом вопрос остаётся открытым, «я выдаю ноль в качестве результата своих недолгих попыток в этом направлении».

 

1. Метаматематический фундамент: от программы Гильберта и теорем Гёделя к теории сложности

В первой трети XX века Давид Гильберт выдвинул программу обоснования классической математики, призванную преодолеть кризис парадоксов теории множеств без интуиционистского отказа от закона исключённого третьего (tertium non datur) и актуальной бесконечности.

Суть метода Гильберта, систематизированного совместно с Паулем Бернайсом в знаменитом двухтомном труде «Основания математики» (Grundlagen der Mathematik, 1934, 1939), заключалась в полной формализации математических теорий — переводе содержательных суждений и умозаключений в систему аксиом и строгих правил вывода, благодаря чему само математическое доказательство превращалось в наглядно обозримую конечную фигуру, подлежащую исследованию финитными методами новой науки – метаматематики, или теории доказательств.

Гильберт ставил три взаимосвязанные сверхзадачи: 1) обосновать полноту формализованных теорий, выводимость любого истинного утверждения, 2) установить их непротиворечивость финитными средствами, невозможность вывода противоречия вида , и 3) решить проблему разрешимости, Entscheidungsproblem — поиск универсального метода, позволяющего за конечное число шагов распознать общезначимость или выводимость любой логической формулы.

Ответом на программу Гильберта стали работы Курта Гёделя 1930–1931 годов и последовавшие за ними результаты А. Чёрча, А. Тьюринга и А. Тарского.

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

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

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

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

Формулируя «Вопрос о поиске доказательств», Д.Л. Гуринович спрашивает: найдётся ли универсальный алгоритм-решение , способный для произвольной предоставленной ему формальной теории и произвольного утверждения  находить доказательство , не превышающее заданного размера  (если таковое имеется), либо останавливаться с ответом 0 (если доказательства в пределах размера  нет), затрачивая на это время (количество шагов), ограниченное полиномом от размера входных данных и параметра ?.

Для формализации этой постановки в работе марта 2017 года вводятся специальные расширения классов сложности —  и :

• Класс : задаётся алгоритмом проверки , где из входного аргумента явно выделен позиционный (например, десятичный) числовой параметр предельного размера доказательства , ограничивающий допустимую длину сертификата неравенством , а время работы самой проверки ограничено полиномом .
• Класс : включает задачи из , для которых существует детерминированный алгоритм-решение , возвращающий за полиномиальное от и величины  время  либо подходящее доказательство  (при  и ), либо 0 при его отсутствии; в частном случае, когда , класс  переходит в классический класс .

Преемственность с идеями Гильберта проявляется у Д.Л. Гуриновича уже в анализе метаматематической связи между проблемой непротиворечивости и гипотезой , Раздел 3 работы «Программа Гильберта, , Рефлексия». Рассматривая задачу проверки доказательств  в теории первого порядка  (например, арифметике Пеано), Д.Л. Гуринович приходит к выводу о том, что сложность доказательства неравенства  на базе теории  не уступает сложности доказательства непротиворечивости самой теории .

В самом деле, в исчислении высказываний тождественно истинной, тавтологией, является формула:

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

Следовательно, любое строгое доказательство несводимости поиска выводов в теории  к классу  неявно опирается на непротиворечивость  — а значит, по Второй теореме Гёделя, требует выхода в более сильную метатеорию или использования метаматематических средств.

2. Модернизация аппарата Гёделя: алгоритмическая диагонализация и упрощённый вывод теорем о неполноте

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

В классическом изложении Гильберта и Бернайса (Том 2, Глава IV, § 1 и Глава V, § 1–2) построение первой и особенно второй теорем Гёделя требовало сложной арифметизации примитивно-рекурсивного отношения выводимости  и предиката доказуемости , а также проверки трёх «условий выводимости» Гильберта — Бернайса для формализма :

1. ;
2. ;
3. .

Д.Л. Гуринович в своих исследованиях отмечает, что эта громоздкость во многом вызвана тем, что Гёдель работал с предикатами и унарно-числовыми гёделевыми номерами.

Переходя к компьютерной интерпретации  , где формулы, доказательства и программы представлены символьными строками в памяти ЭВМ, Д.Л. Гуринович заменяет базовый двухместный предикат проверки доказательства на алгоритм (терм-функцию) , возвращающий значение 1, если текст  является корректным доказательством утверждения с текстом , и 0 в противном случае.

Тогда предикат доказуемости принимает вид равенства под квантором существования:

а недоказуемость записывается как .

 

Алгоритмическая лемма о диагонализации и практическое самоприменение

Опираясь на канторовско-гёделевскую процедуру диагонализации, Д.Л. Гуринович формулирует в Разделе 5 работы «Программа Гильберта, , Рефлексия» два базовых утверждения для алгоритмов:

1. Лемма о диагонализации (п. 5.1): для произвольного одноместного алгоритма найдётся алгоритм без аргументов , такой что результат его работы совпадает с применением  к собственному программному тексту :

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

2. Теорема о построении алгоритма, применяемого к себе (п. 5.2): на базе произвольного алгоритма с одним аргументом можно сконструировать алгоритм без внешних аргументов , который помещает в свою внутреннюю переменную  собственный исходный программный код и работает с ним так же, как  работает с входным аргументом .

 

В отличие от чисто теоретических работ по математической логике, Д.Л. Гуринович иллюстрирует теорему о диагонализации действующей программной реализацией, создавая на языке VBA (MS Word) вспомогательный генератор string_let_code() и самовоспроизводящуюся программу Sub dolly(), которая через обработку кодов кавычек Chr(34) и оператор Replace формирует в переменной x и выводит на экран свой собственный исходный текст. Тем самым гёделевская самореференция предстаёт в работе как прикладная инженерная процедура работы программы со своим кодом.

 

Компактное изложение Первой и Второй теорем Гёделя о неполноте

В Приложениях 8.1 и 8.2 работы марта 2017 года Гуринович применяет вышеуказанный алгоритмический формализм для сокращённого вывода обеих теорем Гёделя. Применяя диагонализацию к предикату недоказуемости , он получает гёделевское утверждение  с текстом , удовлетворяющее эквивалентности:

Если предположить, что  доказано некоторым текстом , то одновременно истинны  (по эквивалентности) и , что даёт противоречие в непротиворечивой теории.

Для вывода же Второй теоремы Гёделя («Если в рамках теории имеется доказательство её непротиворечивости , то теория противоречива») Гуриновичу требуется получить внутри теории импликацию , откуда по принципу контрапозиции  и эквивалентности  следует .

Вместо проверки условий выводимости для предикатов, Д.Л. Гуринович использует тот факт, что  — это алгоритм, и вводит алгоритм , который к любому тексту доказательства  для  достраивает вывод до противоречия . Далее записывается алгоритмическое равенство с тернарным условным оператором :

По мысли Д.Л. Гуриновича, это равенство верно при любом : если  не доказывает , обе части равны ; если же  доказывает  (), то  доказывает , и обе части возвращают 1³. После этого вывод проводится в пять шагов по правилам «Оснований математики» Гильберта и Бернайса (Том 1, Глава IV, § 2, п. 4 и Глава V, § 1):

1. Вводится дедуктивная гипотеза , подстановка которой в правую часть равенства даёт .
2. По теореме дедукции гипотеза переносится в посылку импликации (с заменой переменной на ): .
3. По основной формуле исчисления предикатов  из книги Гильберта и Бернайса записывается аксиома для частного случая: .
4. По правилу силлогизма из шагов 2 и 3 выводится: .
5. Применение правила вывода для квантора существования () даёт: , что в принятых сокращениях означает .

Отдельное внимание Д.Л. Гуринович уделяет понятиям -непротиворечивости и внешней непротиворечивости, рассмотренным в Главе V (§ 1, п. б, в) второго тома «Оснований математики» Гильберта и Бернайса. Опираясь на доказательство непротиворечивости формальной арифметики  через теорию-инструмент  с правилом бесконечной индукции (в изложении Э. Мендельсона), Д.Л. Гуринович поясняет, что арифметика Пеано обладает свойством внешней непротиворечивости: поскольку для каждого конкретного текста  выводимо , теория может быть непротиворечиво расширена аксиомой .

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

3. Гёделевская неполнота в классах сложности: задачи «Сфинкс», «Эдип», язык LS и аргументация в пользу NP != P

Центральным построением первого этапа исследований Д.Л. Гуриновича (2017 год) стало применение гёделевской конструкции неполноты к проблеме . В мартовской статье Д.Л. Гуриновича от 2017 года эта концепция изложена на языке «задач» и аллегорических алгоритмов («Сфинкс», «Эдип», «АнтиЭдип»), а в сентябрьской работе 2017 года, «Языки логики и классы сложности. Рефлексия. », переведена в термины формальных языков (L, LA, LS), сертификатов и классов сложности.

Прикладные роли языка и неравенство

Чтобы связать статическое множество слов (формальный язык) с работой алгоритмов, Д.Л. Гуринович вводит понятие «прикладные роли языка»:

1. Первая прикладная роль (полная): задаётся алгоритмом проверки , который работает полиномиальное время относительно размера своих аргументов и  и устанавливает взаимно-однозначное соответствие между принадлежностью слова  языку и наличием подтверждающего сертификата (доказательства) , при котором .
2. Вторая прикладная роль («эталон»): сопоставляет результаты работы произвольного проверяемого алгоритма-решения (который в корректном случае обязан останавливаться и выдавать 1 или 0 без сертификата) с фактом принадлежности слова  языку.
3. Третья прикладная роль: возникает в случае, если существует корректный алгоритм-решение , выдающий верный эталонный ответ за полиномиальное от время, что по определению означало бы принадлежность языка класса  классу сложности .

 

Сначала Д.Л. Гуринович рассматривает проблему на уровне формальной логики — без полиномиальных ограничений, требуя лишь конечности (финитности) вычислений. Он вводит класс сложности  (аналог  без полиномиального ограничения на размер сертификата  относительно , куда входит язык теорем теории Пеано ) и класс  (финитные разрешимые языки — аналог , куда относится логика высказываний).

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

• если возвращает любой результат, кроме 0 (или в переборе обнаружено доказательство ), то  возвращает 0 (опровергая );
• если возвращает 0, то  возвращает 1 (делая утверждение  истинным и доказуемым);
• если не останавливается,  также не останавливается, и благодаря параллельному перебору утверждение  в непротиворечивой теории не является словом языка .

Далее Д.Л. Гуринович конструирует модифицированный язык логики  (совпадающий с  по множеству слов, ), меняя его первую прикладную роль с  на персонализированный алгоритм проверки , где сертификат разбит на два аргумента:  (программный код алгоритма-решения  либо символ -) и  (текст доказательства). При совпадении аргументов с шаблоном  алгоритм проверки «очень быстро», за полиномиальное число шагов от  и , независимо от , возвращает 0, сообщая алгоритму : «Для алгоритма  нет решения у разбираемого утверждения». Поскольку ни один алгоритм  не может получить корректного ответа о слове , язык  не сводится к классу , что даёт теоретико-сложностную запись теоремы о неопределимости:

Здесь проявляется отличие корректного алгоритма от формальной теории, на котором строит свои рассуждения Д.Л. Гуринович: когда в теории нет доказательства, считается, что «теория не знает», но корректный алгоритм-решение обязан остановиться с негативным результатом 0 («не могу найти доказательство»). Однако как только  останавливается с ответом 0, он на причинно-следственной оси сам создаёт доказательство утверждения  для других алгоритмов (при ), обнаруживая собственную неполноту.

Авторизуемые задачи («Сфинкс»), язык  и схема доказательства

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

Чтобы обойти это ограничение, Д.Л. Гуринович вводит понятие «авторизуемых задач из » (в отличие от «классических задач Кука») и строит задачу проверки «Сфинкс»  — или, в терминах второй статьи 2017 года, язык  с алгоритмом проверки . Конструкция опирается на наличие двух параметров размера в слове :

• — текст доказываемого утверждения на языке теории Пеано²;
• — числовой параметр длины доказательства, записанный в позиционном (десятичном) виде;
• — строковый параметр длины доказательства, представляющий собой в корректном случае унарную строку из символов 1 длиной  (, где , что экспоненциально больше размера позиционной записи );
• — сертификат, состоящий из программного кода алгоритма-решения  (или -) и текста доказательства , чей суммарный размер ограничен полиномом от длины строки : .

Работа алгоритма проверки  (и аналогично «Сфинкса» ) организована в четыре этапа с двумя ограничивающими полиномами на время работы:

1. Этап 1 (Персональная подсказка — случай 6.1): до обращения к потенциально огромным аргументам и  алгоритм  проверяет аргументы  на совпадение с шаблоном . Если совпадение выявлено,  возвращает 0 за полиномиальное количество шагов , зависящее только от  и , без рассмотрения аргументов  и .
2. Этап 2 (Контроль размеров — случай 6.2): проверяет, что (состоит только из  единиц) и что ; при несоответствии возвращает 0.
3. Этап 3 (Контроль шаблона ): проверяет, что соответствует шаблону — либо .
4. Этап 4 (Базовая проверка): исполняет стандартный алгоритм проверки доказательств в пределах времени .

 

Согласно построению Д.Л. Гуриновича на примере языка  (Раздел 6 статьи сентября 2017 года и Раздел 7 статьи марта 2017 года), аргументация в пользу неравенства  разворачивается в четыре шага:

1. Требование ускоренного ответа от алгоритма-решения: Поскольку в специальном случае 6.1 алгоритм проверки отвергает слово за время  без обращения к  и , Гуринович постулирует, что при сведении задачи к классу  корректный алгоритм-решение  (способный получить свой собственный код  методом диагонализации) обязан выдать единственно возможный для него непротиворечивый ответ 0 за полиномиальное от тех же значимых аргументов количество шагов:При этом  обращается к строке  не более чем в  позициях.
2. Эмуляция строки без её физического генерирования: Чтобы перевести работу  в короткое формальное доказательство (не тратя экспоненциальное число шагов на генерацию строки ), Д.Л. Гуринович заменяет алгоритм  на модернизированный алгоритм без аргументов  (через вспомогательный ), в котором каждое обращение к -му символу строки  заменяется обращением к функции , возвращающей символ 1 при  и признак выхода за пределы данных при  или ². Так как  делает  шагов, размер логического вывода равенства  оценивается композицией полиномов , а доказательство равенства  имеет размер не более .
3. Применение аксиомы равенства Гильберта — Бернайса (): работа опровергающего алгоритма описывается внутри теории равенством . Подставляя это равенство в аксиому равенства  из первого тома «Оснований математики» при  и , автор за фиксированное число шагов выводит импликацию:размер доказательства которой с учётом подстановки конкретного  ограничен полиномом .
4. Сопоставление полинома от и полинома от : Соединяя по аксиомам равенства и правилу Modus Ponens выводы шагов 2 и 3, Гуринович строит формальное доказательство  утверждения , суммарный размер которого  ограничен полиномом от длины позиционной записи числа :В то же время в языке  (при независимом от кода решателя сертификате ) допустимый размер доказательства ограничен величиной . Поскольку длина унарной строки  растёт экспоненциально относительно количества десятичных цифр , при достаточно больших  выполняется неравенство:Это означает, что для достаточно больших  слово  принадлежит языку  (имеет доказательство допустимой длины), тогда как алгоритм  выдал для него ответ 0, проявив свою неполноту². Ввиду произвольности  автор заключает, что свести язык  к классу  невозможно.

Критика теоремы Кука и границы применимости авторского подхода

Существенным элементом научной концепции Д.Л. Гуриновича является его полемика вокруг теоремы Кука о сводимости задач класса  к выполнимости булевых формул (КНФ/ДНФ) в логике высказываний.

Д.Л. Гуринович утверждает, что теорема Кука применима только к «классическим задачам из » (задачам Кука), в которых аргумент долга  незначим (равен -), а информация одинакова для всех алгоритмов-решений.

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

Ссылаясь на Первый том «Оснований математики» Д. Гильберта и П. Бернайса (Глава IV, § 1 «Введение индивидных переменных…» и Глава V, § 1, п. 5 «Добавление функциональных знаков; понятие терма»), Д.Л. Гуринович подчёркивает, что логика высказываний (КНФ/ДНФ) обходит стороной связь между субъектом и предикатом и не содержит ни индивидных переменных, ни функциональных знаков, термов. Чтобы распознать «персональную подсказку» для себя в задаче «Сфинкс», алгоритм-решение должен осуществлять выбор на основе терма в теории первого порядка с равенством, вследствие чего авторизуемая задача не сводится к одной универсальной КНФ или ДНФ на все алгоритмы-решения.

Вместе с тем в Разделе 7 работы сентября 2017 года «О классическом доказательстве  (эвристически)» Д.Л. Гуринович прямо отмечает ограничение своей конструкции с точки зрения классической постановки проблемы: в классическом случае у алгоритма проверки имеется только один ограничивающий полином  (без второго ускоренного режима  и без использования собственного программного кода решателя ). Если разрешить алгоритму  работать в пределах «обычного» полинома , то прямой протокол его работы окажется в фиксированной степени больше предельного размера доказательств . Хотя Д.Л. Гуринович высказывает эвристическое предположение, что повторяющиеся отрезки исполнения алгоритма в таком протоколе можно сжать за счёт неполиномиального подбора производных правил вывода и сокращений, он констатирует, что для доказательства в рамках классического подхода ему «не хватает в настоящий момент ни времени, ни знаний, ни сил».

4. Ревизия оснований Гильберта и Гёделя: критика гёделизации, арифметики Пеано и тезиса Чёрча — Тьюринга

Попытки отстоять свой подход к  в научных дискуссиях и на математических форумах (в том числе ответы на вопрос «почему вы не используете гёделевы номера?») привели Д.Л. Гуриновича в 2020–2025 годах к выводу о том, что классический формализм арифметики Пеано и теории вычислимости, унаследованный от Гильберта, Гёделя, Чёрча и Тьюринга, не обладает достаточной выразительностью для описания размера данных, частичного чтения аргументов и времени работы компьютерных программ. Это побудило Д.Л. Гуриновича перейти от использования классической метаматематики к попытке её фундаментальной реконструкции.

 

Элемент классического аппарата	Роль у Гильберта, Бернайса и Гёделя	Выявленный Д.Л. Гуриновичем дефект в теории алгоритмов и вычислимости	Предложенная Д.Л. Гуриновичем замена (2020–2025 гг.)
Стандартная интерпретация ()	Наглядное финитное построение цифр 1, 11, 111 («счётные палочки») путем приписывания 1 (Гильберт, Бернайс, Т. 1, Гл. II, § 1).	Экспоненциальное раздувание размера данных по сравнению с позиционной записью (число 11234 требует блока из более чем 11000 единиц); невозможность частичного чтения без потери полиномиальности.	Компьютерная интерпретация () и позиционные системы счисления внутри типированной теории строк1.
Гёделева нумерация (арифметизация)	Кодирование формул и выводов через степени простых чисел  (Гильберт, Бернайс, Т. 2, Гл. IV, § 1).	Декодирование (разложение числа на простые сомножители) относится к неполиномиально сложным задачам; конкатенация текстов сводится к громоздким умножениям и сложениям.	Прямое представление формул, программ и выводов как символьных строк в арифметике строк без кодирования числами.
Частично рекурсивные функции (ЧРФ)	Уточнение интуитивного понятия вычислимой функции в арифметике (Гёдель, Клини, тезис Чёрча 1936 г.).	Базовые функции (нулевая, , ) и операторы рекурсии читают аргумент целиком; невозможно представить алгоритм, отвергающий большой вход по первому символу.	Аксиоматика разбиения строк , критерии локального сравнения, вставки и извлечения данных.
Абстрактная арифметика Пеано ()	Универсальная база для представления рекурсивных функций и метаматематики (система  / ).	Описывает лишь общие свойства всех интерпретаций (включая бесконечные невычислимые периодические строки); отождествляет числа разных систем счисления (), лишая число длины.	Арифметика строк с типированными кванторами , аксиомами нарушения равенства  и явным приведением типов .
Классический синтаксис предикатов и функций	Свободные функциональные символы , вводимые по условию существования и единственности .	Позволяет через взаимно-однозначную перекодировку определить «анти-функции»  и , меняющие местами двоичную и десятичную запись и создающие логически эквивалентную теорию .	ООП-расширение математической логики: привязка свойств и методов к объекту (a.l() = 3_D, b.l() = 111_B).
Машина Тьюринга (МТ)	Абстрактный вычислитель на линейной ленте с внешним перечнем состояний  и правил перехода.	Программа отделена от ленты данных; для доступа ко второму аргументу «тележка» вынуждена проехать всю длину первого аргумента (отсутствие передачи по ссылке); неудобство для оценки времени реального ПО.	Машина исполнения компьютерных алгоритмов (МКА) с центральным процессором, неограниченными лучами данных и программным текстом на луче Program.

Критика частично рекурсивных функций и построение Теории строк (2020)

В 84-страничной работе «Теория строк (слов). Недостаточная выразительность рекурсивных функций и арифметики для теории алгоритмов» (25 апреля 2020 года) Д.Л. Гуринович обосновывает тезис о том, что аппарат частично рекурсивных функций (ЧРФ), на котором со времён Гёделя, Клини и Чёрча строилась представимость алгоритмов в арифметике, не отражает современную сложность реальных вычислений.

Анализируя в подразделе VI базовые примитивно-рекурсивные функции (нулевую функцию, функцию следования , функции проекции ) и операторы суперпозиции, примитивной рекурсии и минимизации аргумента, Гуринович указывает, что ни одна базовая функция и ни один оператор не могут работать с начальной частью своего входного аргумента, не читая его «хвоста» до конца (так как для увеличения или уменьшения числа на 1 необходимо прочитать входной аргумент целиком). Напротив, реальный алгоритм проверки сертификата в классе  должен самостоятельно контролировать размер сертификата и отбраковывать чрезмерно длинный сертификат при чтении первого же символа за пределами допустимого порога, не тратя время на обработку всего «входа».

Для формального решения этой проблемы Д.Л. Гуринович строит аксиоматическую теорию строк первого порядка с равенством, опираясь на логическое исчисление Д. Гильберта и П. Бернайса, аксиомы импликации, конъюнкции, дизъюнкции, эквивалентности, отрицания, правила кванторов, аксиомы равенства  и теорему дедукции. Ядро теории образуют четыре независимые группы аксиом, причём независимость каждой группы обосновывается построением интерпретаций в метатеоремах (м.5.1), (м.6.1), (м.7.1), (м.8.1):

1. Разбиение строк (аксиомы 1–4): любая строка в произвольной позиции  делится на начальную и конечную части: , причём после -го символа в префиксе находится пустая строка  (, ), а подстрока определяется как .
2. Конечный алфавит (аксиомы 5.1–5.2): Всякий элемент равен некоторому «атому» алфавита , где непустые попарно различные символы нумеруются до фиксированного предела , а при  функция  возвращает .
3. Концы и соединение строк (аксиомы 6.1, 7.1–7.2): Появление пустой строки в позиции  служит критерием окончания строки (), что позволяет определить длину конечной строки  (а для бесконечной строки ) и аксиоматизировать конкатенацию .
4. Посимвольное равенство (аксиома 8.1): .

На этой основе Д.Л. Гуринович вводит определения посимвольного сравнения  через первую позицию отличия , поиска подстроки  и вставки , выводя три ключевых, фундаментальных результата – 1) Критерий локального сравнения (c.9.2), 2) Критерий локальной вставки (т.9.4) и 3) Критерий локального извлечения данных (т.9.5):

Эти теоремы формально выражают тот факт, что если запрашиваемая операция лежит в пределах длины начальной части  (), то результат функции на составной строке  не зависит от присоединённого справа «хвоста» .

Далее в метатеоремах (м.9.1) и (м.9.2) Д.Л. Гуринович приводит доказательство того, что в теории строк с односимвольным алфавитом () и, как следствие, в арифметике невозможно в общем случае представить работу алгоритмов со строками многосимвольного алфавита так, чтобы размер логического вывода находился в полиномиальных (или любых иных) пределах от времени работы алгоритма. Если алгоритм проверки русского правописания отвергает роман по первой же букве Ъ, то в односимвольной (унарной) записи 000…0 никакой вывод на основании фиксированной начальной части длины  невозможен: иначе все романы, представленные унарными строками длины , начинались бы на Ъ, а для бесконечного множества романов, не начинающихся на Ъ, осталось бы лишь конечное число вариантов строк длины меньше .

Критика эквивалентности вычислимости по Тьюрингу и рекурсивных функций (2022–2023)

В работах «Вычислимость по Тьюрингу превосходит в принципиальном отношении вычислимость рекурсивных функций» (август 2022 года) и «Числа арифметики Пеано не обладают необходимыми для вычислимости свойствами…» (январь 2023 года) Д.Л. Гуринович подвергает ревизии классическое положение теории вычислимости о совпадении множества функций, реализуемых на машинах Тьюринга, и множества частично рекурсивных функций.

Аргументация Д.Л. Гуриновича опирается на понятие «числа-строки», которое обладает одновременно свойствами натурального числа (подчиняясь аксиомам арифметики) и свойствами строки (имея вычислимую длину и посимвольный состав в конкретном представлении).

На ленте машины Тьюринга одно и то же натуральное число имеет разную длину при разных способах записи:

• число 5681245567 имеет в десятичной записи длину 10, а в шестнадцатеричной записи (152a0ed7f) — длину 9;
• число 10 имеет в десятичной записи длину 2, в двоичной (1010) — 4, а в стандартной унарной интерпретации Гильберта (00000000000) — длину 11;
• функция взятия первого символа для числа 15 даёт в десятичной записи , а в шестнадцатеричной — .

В рамках же абстрактной арифметики Пеано разные представления одного числа (например, десятичное  и двоичное ) равны между собой () и выступают одним и тем же объектом, поэтому никакая рекурсивная функция от этого аргумента не может выдать для него два разных значения длины или разные первые символы. Стандартное доказательство сводимости машины Тьюринга к рекурсивным функциям (например, в книге Дж. Булоса и Р. Джеффри «Вычислимость и логика», где левый и правый лучи ленты МТ рассматриваются как числа  и ) неявно использует внешнее по отношению к арифметике соглашение о смысле и способе записи чисел. Кроме того, Д.Л. Гуринович строит невычислимые бесконечные интерпретации арифметики Пеано, например, сопоставляя числу  бесконечную периодическую строку 1111..101111..10… с повторяющимся блоком из  единиц и одного нуля, которая удовлетворяет аксиомам Пеано, но не может быть обработана за конечное время.

Полемизируя со статьёй Дж. Коркорана, У. Франка и М. Малони «String Theory» (The Journal of Symbolic Logic, 1974), где обосновывалась «синонимичность» теории строк Гермеса  и Тарского арифметике второго порядка, Д.Л. Гуринович утверждает, что при наличии в теории нескольких типов чисел-строк обычная аксиома арифметической индукции  перестаёт быть истинной. В качестве контрпримера он рассматривает формулу  («десятичная длина числа-строки  равна числу , приведённому к десятичному типу»):

1. База индукции для нуля стандартной унарной интерпретации  истинна, так как число 2 в унарной записи имеет вид 000 и его длина равна .
2. Индуктивный переход также оказывается истинным для всех типов чисел-строк: для унарного типа  истинны и посылка, и заключение (длина унарной записи всегда на 1 больше величины числа), а для любой позиционной записи  () посылка  всегда ложна (позиционная запись начиная с 1 короче унарной), что делает импликацию истинной.
3. Заключение оказывается ложным, так как не выполняется для позиционных типов чисел-строк.

Взамен абстрактной арифметики Пеано Гуринович предлагает аксиоматику «Арифметики строк»:

• Предметные переменные и кванторы арифметики снабжаются индексом типа (где  соответствует унарной записи,  — -ичной позиционной системе счисления, а индексы вида  — строкам без числовых свойств)³. Типированный квантор общности определяется через пустую строку на нулевом месте: .
• Аксиомы теории () и схема индукции () записываются с типированными кванторами отдельно для каждого типа : .
• Формулируются аксиомы нарушения равенства из-за строковых свойств (): строки и числа-строки разных типов не равны между собой (); равенство хотя бы одной пары символов из двух алфавитов влечёт полное совпадение алфавитов и нулей (аксиома ), а для перевода числа из типа  в тип  с сохранением числовой величины вводится оператор приведения типов  по аналогии с языком Си с аксиомами   и  .

Расширение математической логики средствами ООП (2025)

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

Даже если в теории  заданы переменные  (с длиной ) и  (с длиной ), в рамках классической логики первого порядка (по Следствию 3.3 из книги Э. Мендельсона о введении новых функциональных букв при доказанном условии существования и единственности) благодаря взаимно-однозначной функции перекодировки между представлениями чисел можно определить «анти-функции»  и , которые «видят» вместо десятичного представления двоичное и наоборот:  и . Поскольку классическая логика не привязывает функции к объектам, теория  с аксиоматизированными функциями  оказывается логически эквивалентной исходной теории  с точностью до переименования функций.

Чтобы преодолеть эту неоднозначность «логически эквивалентных» наборов функций, Гуринович предлагает расширить формальную логику синтаксисом и семантикой объектно-ориентированного программирования (ООП), восходящего к языку Smalltalk-80 Алана Кэя и Дэна Ингаллса. При записи длины строки как привязанного к объекту свойства с фиксированным именем l (a.l() = 3_D и b.l() = 111_B) альтернативное свойство с именем l_1 отсутствует, а попытка приписать тому же свойству .l() перевёрнутые значения (a.l() = 111_B и b.l() = 3_D) вступает в прямое противоречие с исходными равенствами.

5. Инженерно-математическое воплощение финитизма: ашина исполнения компьютерных алгоритмов, Русская машина Гуриновича (МКА)

Финитная установка Гильберта предполагала, что за формальной теорией стоит наглядная, конструктивно описываемая модель (интерпретация), обеспечивающая непротиворечивость аксиом и связь с реальностью. Считая машину Тьюринга неадекватной современным вычислительным системам и неудобной для оценки времени работы программ, Д.Л. Гуринович в 120-страничной работе от 16 марта 2021 года конструирует стандартную интерпретацию для своей теории компьютерных строк — «Машину исполнения компьютерных алгоритмов» (МКА).

Ключевая архитектурная особенность МКА состоит в том, что сам алгоритм, программный текст, является одной из входных символьных строк, расположенной на выделенном луче данных Program, а номер позиции первого символа текущей команды хранится в десятичном представлении (разрядом единиц в первой ячейке) на луче i_Program. Благодаря этому программный текст, его использование в качестве алгоритма и время его исполнения становятся в МКА такими же объектами исследования теории компьютерных строк, как и обрабатываемые данные.

 

Масштабирование памяти без ограничения разрядности и языки SI / SMAU

В модели МКА Д.Л. Гуринович предлагает решение проблемы масштабирования реальных вычислительных систем, память которых на практике ограничена разрядностью адресации процессора (например, предел в 4 Гб для 32-разрядных процессоров или конечность адресного пространства в сетях).

Центральный процессор МКА имеет фиксированную разрядность и непосредственно обращается только к своим регистрам (Command, Source_1, Target_1, Continue_0 и др.) и начальным частям конечного числа лучей данных. Каждая ячейка луча данных устроена как автономный узел, способный обмениваться сообщениями лишь с двумя соседними ячейками (а первая ячейка — со второй ячейкой и процессором). Обращение к удалённой ячейке с произвольно большим номером осуществляется путём передачи пакета сообщений по эстафете от узла к узлу с поразрядным уменьшением передаваемого числа вплоть до установки указателя p1 = 1 в нужной ячейке.

Функционирование МКА описывается на трёх уровнях формальных языков:

1. Стандартный язык SI (Язык стандартной интерпретации): язык программирования среднего уровня для записи алгоритмов на луче Program. Содержит метки [next1];, переходы goto x1;, остановку .;, команды присваивания с дописыванием в конец x1() = …;, полной заменой строки x1(0) = …; или вставкой с позиции x1(x2) = …;, а также базовые функции len(x1), Chr(x1), Value(x1), from(x1, x2), str(x1, x2, x3), Comp(x1, x2), Next(x1), Previous(x1).
2. Аппаратный язык SI: расширение языка SI, на котором написан «аппаратный интерпретатор» в ПЗУ процессора. Включает свойства .Register и .SRegister, оператор косвенной адресации луча @ (@Source1), команды ожидания wait;, wait_i;, отправки сообщений SendTo_i и переключения режимов Setmode SMAU; / Setmode SI;.
3. Язык SMAU (ОССУ — язык одновременных сообщений соседним узлам): событийный язык без циклов и переходов для написания обработчиков сообщений в процессоре и ячейках. Каждая ячейка содержит регистры основного значения rv, теневого значения sv, указателей p1, p2, флагов увеличения/уменьшения ic, dc, флага MayBe1 и признака первой ячейки IsFirst.

Для бесконфликтной передачи пакетов и аксиоматизации времени в МКА применяются два механизма:

• Сетки синхронизации и уход пакетов «в бесконечность»: Передача сообщений синхронизирована по двоичным сеткам с интервалом моментов ( — 1 момент,  —  момента, вплоть до  —  момента, или «1 мгновение»)³. Эстафетные сообщения от процессора отправляются не чаще чем через 1 момент (скорость 1 ячейка за 1 момент), чтобы новые эстафеты не догоняли старые³. Когда пакет данных выполняет свою задачу (уменьшаемое число стало равно 1), тип сообщения переключается на «холостой» режим (/# Разряды для уменьшаемого числа исчерпаны с перебором (p1) #/), и пакет продолжает уходить по лучу в бесконечность, не производя изменений в остальных ячейках.
• Теневой канал связи и оперативное завершение протокола: чтобы избежать конфликтов, когда один луч данных одновременно выступает источником и получателем, каждая ячейка имеет два независимых канала — основной (rv) и «теневой» (sv). При этом протокол передачи считается оперативно завершённым относительно процессора тогда, когда окончательный результат сформирован в 1-й ячейке, а в остальных ячейках формируется по мере удаления волны от процессора со скоростью не менее 1 ячейки за 1 момент.

Такая организация позволяет строго оценить время выполнения команд языка SI: при работе с неограниченными лучами данных время выполнения каждой команды зависит линейно от размера используемых в ней данных (плюс константа  на работу в пределах регистров процессора). Вместе с тем учёт геометрии расположения данных на луче и конечной скорости света приводит Д.Л. Гуриновича к выводу о том, что для больших объёмов данных время сортировки  элементов на одномерном луче данных составляет не менее порядка  единиц времени даже для быстрых алгоритмов сортировки (оценка  справедлива лишь для ограниченной памяти, где время доступа к любой ячейке считается константой).

6. Философское и социокультурное наследие: «рефлексивная логика», антииндивидуализм и ноология

Подобно тому как теоремы Гёделя о неполноте породили обширную философскую традицию, Д.Л. Гуринович выстраивает на основе своих математических работ собственную мировоззренческую и социологическую концепцию, которую он в 2017 году обозначает как «рефлексивную логику», а в работе 2026 года развивает в учение о закономерностях функционирования разума — «ноологию».

Формализация «Я», свободы воли и «коллективного алгоритма»

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

В рамках «рефлексивной логики» Гуринович формулирует четыре философских обобщения:

1. Определение субъектности через границу ограничения: В языке конкретному алгоритму-решению  ставится в соответствие урезанный набор сертификатов, из которого отброшены недоступные ему подтверждающие доказательства. Отсюда автор выводит тезис: «Быть кем-то — это не иметь чего-то такого, что есть в мире, но при этом отделено от тебя какой-то границей».
2. Соотношение дескриптивных законов природы и нормативных требований «долга»: если базовая проверка (при аргументе долга «объективно») подобна дескриптивным законам природы, которым подчиняются все объекты, то персональная подсказка в «аргументе долга» носит нормативный характер — ей подчиняется лишь выборка тех алгоритмов, которые способны распознать требование к себе и исполнить его.
3. Критика «демона Лапласа» и алгоритмическая природа свободы воли: ощущение свободы воли и непредсказуемости собственных мыслей возникает даже в детерминированном мире потому, что субъект «не может во всём опередить себя самого» на задачах самоприменения. Равным образом опровергается всеведение «демона Лапласа»: чтобы знать систему , наблюдатель должен отличаться от , а при попытке демона Лапласа изучить собственный мозг материальные процессы запоминания будут изменять состояние мозга сильнее, чем оно было познано (по неформальной оценке автора, система не может знать больше половины информации о себе самой).
4. Критика индивидуализма и концепция «коллективного алгоритма»: Вторую теорему Гёделя о неполноте Д.Л. Гуринович интерпретирует как математическое опровержение самодостаточного индивидуализма: теория, доказавшая собственную правоту («непротиворечивость»), является противоречивой. В задаче «Сфинкс» отдельный алгоритм не способен сам подтвердить истинность , но его оперативный ответ 0 («я не справлюсь с этим в такие сроки») служит необходимым промежуточным звеном («полуфабрикатом»), позволяющим другим алгоритмам в составе единого «коллективного алгоритма» быстро построить полное доказательство истинности .

Историософия науки: судьба школы Гильберта и «общественный наследственный код»

В работах 2017–2026 годов Д.Л. Гуринович анализирует исторические и социальные причины того, почему за взлётом математической логики в эпоху Гильберта и Гёделя последовал длительный спад интереса к основаниям математики и разрыв между чистой математикой и сферой ИТ. В его текстах выделяются три ключевых фактора:

• Разрушение немецкой математической школы и гибель Тьюринга: в статье января 2023 года автор подробно останавливается на роли немецкого математического сообщества второй половины XIX — первой трети XX века (от Гаусса и Георга Кантора до Феликса Клейна, Давида Гильберта, Эмми Нётер и главы университетского отдела министерства образования Пруссии Фридриха Альтхоффа). По оценке Д.Л. Гуриновича, насильственное уничтожение этого сообщества накануне и в ходе Второй мировой войны, а также последующее уголовное преследование и гибель Алана Тьюринга в Англии прервали «период логических открытий»: после смерти Гильберта и распада гёттингенской среды даже Гёдель перестал отвечать на самые принципиальные вопросы оснований математики, поскольку их больше никто не ставил на уровне Гильберта.
• Профессиональная деформация «формализма»: сопоставляя историю создания общей теории относительности, где физик А. Эйнштейн выбрал адекватный реальности формализм, а математик Г. Минковский в переписке с Гильбертом шутил о необходимости «очиститься» после общения с физиками и вернуться к математическому способу мышления, Д.Л. Гуринович отмечает склонность математиков работать исключительно внутри принятых в сообществе абстрактных конструкций, отбрасывая «лишние» свойства реального мира. В результате, когда в компьютерную эпоху потребовалось перенести из реальности в математику свойства вычислимых строк и времени работы алгоритмов, академическое сообщество продолжило опираться на невычислимые абстракции арифметики Пеано, предложив взамен реформировать подготовку кадров путём обучения практикующих программистов формальной логике.
• Утрата «общественного наследственного кода» и идеологический барьер (работа 2026 года): в работе марта 2017 года Д.Л. Гуринович высказывает мысль о том, что откат от достигнутого уровня логики произошёл потому, что теоремы Гильберта, Гёделя, Тьюринга и Тарского о неполноте и неразрешимости вошли в мировоззренческий конфликт с доминирующим в XIX–XX веках индивидуалистическим трендом, отвергающим внешние ограничения над отдельным разумом. В работе «Причины научно-религиозного и демографического тупиков современного общества и вопрос об их преодолении» от 26 июля 2026 года) этот тезис обобщается Д.Л. Гуриновичем в рамках концепции «общественного наследственного кода» — небиологической системы передачи знаний и этики общественного долга, которую исторически поддерживали аристократическая и религиозная страты. Устранение этих страт и возобладание биологического индивидуализма, «извращенизации», привели, по мнению Д.Л. Гуриновича, сначала к прекращению века фундаментальных научных открытий (с переходом к механической эксплуатации прежних теорий), а затем и к демографическому кризису, преодоление которого требует возврата к приоритету теоретического разума и коллективного служения.

Послесловие Научного руководителя Института фундаментальной математики Дмитрия Леонидовича Гуриновича