dmitgu

4. Рефлексия на языке LA. NF ≠ F.

к Оглавлению

Язык логики и его свойства очень важны для математики, а язык LA является одной из разновидностей языка логики. Поэтому выразим одно его важное свойство, позаимствовав понятие «класс сложности» из теории алгоритмов: 

Язык LA принадлежит классу сложности NF. Это аналог класса NP, только без полиномиальных ограничений. Главное, чтобы алгоритм проверки работал конечное время (был финитным). Наш алгоритм проверки La(t, a, y) можно построить так, чтобы он работал полиномиальное время относительно размеров |t|, |a|, |y|. 

Но в логике время не является принципиальным, а в класс NP язык LA при полиномиально быстром алгоритме La(t, a, y) не попадет, потому что полиномиального ограничения размеров сертификата |a| + |y| от размеров слова |t| нет в общем случае, так как размер корректного доказательства может быть каким угодно – независимо от размера доказываемого утверждения.

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

Так вот, язык LA принадлежит классу сложности NF, а если бы он был разрешим, то его можно было отнести и к классу сложности F – финитных языков (к ним относится, например, логика высказываний), когда о слове за конечное время можно сказать, принадлежит оно языку или нет. Класс F – аналог класса P, но без полиномиальных ограничений. Мы доказали, что LA не сводится к классу F, так как для любого алгоритма-решения Sol(t) есть аргумент:

«AntiSol», о которых алгоритм

Sol(«AntiSol») не может получить корректного ответа как о слове  «AntiSol» (не)принадлежащем языку LA. То есть, доказано:

NF ≠ F

И это неравенство – обобщенный аналог теоремы о неопределимости.

Это – та же теорема о неопределимости из логики, но переписанная в терминах языков и классов сложности. И неразрешимость тут представлена как невозможность языку из одного класса сложности (NF) принадлежать другому классу сложности (F) – несводимость одного класса сложности к другому. Да и множество других теорем о неразрешимости могут быть переписаны как несводимость классов сложности друг к другу. 

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

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

Теория (достаточно выразительная) не может доказать ограничивающее утверждения о себе в целом – это известно из 2-й теоремы Гёделя (теория не отличает себя от противоречивой теории, в которой доказано всё). Но внутри теории вполне доказаны ограничивающие теоремы об алгоритмах. Та же теорема о неопределимости. И эти сведения алгоритмам – если они достаточно выразительны – доступны.

Трудно переоценить важность рефлексии для жизни: Без понимания того, какие опасности грозят именно тебе и какие твои действия могут привести к катастрофе именно тебя – твоя жизнь не была бы сколько-нибудь продолжительной. И возможность формализации данного свойства (рефлексии) в математике – более принципиальна, на мой взгляд, чем неравенство NF ≠ F или NP ≠ P. 

Ещё один интересный момент – когда для конкретного алгоритма-решения в применённом методе использования 1-й прикладной роли языка LA задаётся тот набор сертификатов, который соответствует именно этому алгоритму-решению, а другие сертификаты отбрасываются. Дело в тома, что «быть кем-то» (в данном случае – быть данным конкретным алгоритмом-решением) – это не означает, что ты имеешь свойства, которые не имеет остальной мир: Мир содержит тебя вместе со всеми твоими свойствами. Значит, быть кем-то – это не иметь чего-то такого, что есть в мире, но при этом отделено от тебя какой-то границей. 

Error

default userpic

Your reply will be screened

Your IP address will be recorded 

When you submit the form an invisible reCAPTCHA check will be performed.
You must follow the Privacy Policy and Google Terms of use.