dmitgu

1. «Стандартный» язык логики L. Прикладные роли языка.

к Оглавлению

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

Язык – это просто множество слов, которое само по себе никакого отношения к алгоритмам не имеет. Другое дело, что можно задавать «внешние» отношения между языком и алгоритмами. 

Например, алгоритм проверки, с помощью которого можно описать язык класса NP и отнести подобный язык к классу NP – вовсе не является «частью» языка. Язык можно описать и неполиномиально долгим по своей работе алгоритмом проверки и ещё бесконечным количеством способов. Язык от этого никак не изменится. Поэтому при отнесении языка к классу NP говорят, что соответствующий алгоритм для описания языка «существует», но такой способ описания данного языка вовсе не является обязательным или единственным.

Кстати, те же «сертификаты» («свидетели») тоже не являются частью языка из класса NP – это как раз атрибут некоторого алгоритма проверки, с помощью которого можно описать данный язык. Если бы сертификаты были частью языка, то он заведомо не мог бы относиться к классу P (вопрос о равенстве NP и P тогда не возникал бы) – так как среди алгоритмов, которые могут использоваться для описания языков класса P, обязательно есть («существуют») и такие, которым сертификаты не требуются. 

Рассмотрим язык логики L – для теории Пеано, например. Этому языку соответствует алгоритм проверки Lc(t, y), где t – текст теоремы, а y – текст доказательства. Результат работы алгоритма Lc(t, y) будет 1, если в t – текст утверждения и в y – текст его доказательства. И результат работы алгоритма Lc(t, y) будет 0 в ином случае. 

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

С учётом последнего замечания (об аргументах) алгоритм Lc(t, y) работает полиномиальное время (количество шагов) относительно размера своих аргументов (от количества символов в них). Что не делает язык L языком класса NP, разумеется – так как нет (это доказано для общего случая из теорем Гёделя) полиномиальной (и вообще никакой) связи между размерами теорем и размерами их доказательств.

И данный алгоритм Lc(t, y) может рассматриваться в качестве полной прикладной роли языка L. 

Прикладную роль для данного языка назовём полной, если для каждого слова t данного языка есть соответствующая ему единичная задача с положительным решением Lc(t, y) = 1 для некоторого «доказательства» y теоремы t. И нет никакой единичной задачи с положительным решением для слова t, которое не принадлежит языку. То есть - взаимно-однозначное соответствие между некоторым множеством решаемых задач и множеством слов языка. Для некоторых языков (из класса P, например) в качестве «доказательства» y может выступать и само слово t.

У нас есть множество задач, задаваемых алгоритмом Lc(t, y) для утверждений t, которые оказываются теоремами, если есть соответствующее доказательство y – при котором имеем Lc(t, y) = 1. Имеется взаимно-однозначное соответствие между языком L и задачами, задаваемыми утверждениями t, для которых имеется y такой, что Lc(t, y) = 1. И это – 1-я (Первая) прикладная роль разбираемого нами языка L.

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.