NP≠P. Док-во от противного-контрпример алгоритмов из NP

[dmitgu]

mihaild в сообщении #1275075 писал(а):

Из последнего сообщения я не понял ничего, но, видимо, и не предполагалось.

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

Так вот, если есть слово из двух частей $(w_1, w_2)$, при этом результат понятен из одного только $w_1$, то вместо их пары можно передать только $w_1$ корректному алгоритму - всегда можно "урезать" входную информацию до "достаточного" размера. И вполне себе соответствовать "требованию" расчёта относительно размера входной информации. То есть - это требование об опоре на размер входной информации ничего не меняет, по сути, и всегда можно сводить вопрос к размеру "достаточной" для работы алгоритма входной информации.

Сомневаюсь, что я понятно объяснил для Вас, так как Вы "очень" формалист для того, чтобы я легко догадывался, в чём загвоздка для Вас. Но я стараюсь понять.

[Sender]

dmitgu в сообщении #1275096 писал(а):

Так вот, если есть слово из двух частей $(w_1, w_2)$, при этом результат понятен из одного только $w_1$, то вместо их пары можно передать только $w_1$ корректному алгоритму - всегда можно "урезать" входную информацию до "достаточного" размера.

Можно урезать или нельзя - должен решать сам алгоритм. А на вход он должен получить целое слово оговоренного размера. В противном случае ваши конструкции не имеют ничего общего с понятиями $P$, $NP$ и т.п.

[dmitgu]

Sender в сообщении #1275098 писал(а):

А на вход он должен получить целое слово оговоренного размера.

Он получает слово того размера, какого получает ) И вместо слова $(w_1, w_2)$ ему можно передать слово $w_1$. И если он использует только $w_1$ в своей работе, то он "не заметит", что $w_2$ нет. А у нас как раз речь о том, что в $w_1$ есть вся необходимая информация и его размер - неполиномиально меньше размера $|w_2|$.

Если алгоритм не обращается к $w_2$, то его ответ не зависит от $w_2$ и относится к любому варианту этого $w_2$.

-- 15.12.2017, 17:17 --

З.Ы. Кстати, если хотите не рассматривать мои доводы на основании привычного понимания, то я вообще-то рассматриваю в качестве "входной информации" для алгоритма и его собственный программный код. "Аксиома рефлексии". Этого же не было в учебниках? Но по смыслу-то это тоже - информация! И алгоритм в состоянии её получать процедурой диагонализации. Это особенный вариант? Так и умение пользоваться информацией в своих аргументах - тоже не каждому алгоритму доступно.

[mihaild]

dmitgu в сообщении #1275096 писал(а):

Но не требуйте уж слишком жёстко от меня такой же формализованности, как свойственна Вам - у каждого подхода есть свои минусы и плюсы.

Вместе с формальностью растет объем формулировок и снижается неоднозначность. У ваших формулировок неоднозначность такая, что часто выделить там хотя бы какие-то основные варианты не получается.

Для понимания, как работать со строгими формулировками, почитайте какой-нибудь учебник (например, первую часть "Классических и квантовых алгоритмов" Вялого, Китаева, Шеня).

dmitgu в сообщении #1275096 писал(а):

То есть - это требование об опоре на размер входной информации ничего не меняет, по сути, и всегда можно сводить вопрос к размеру "достаточной" для работы алгоритма входной информации.

Если "достаточная информация" легко выделяется из слова - то можно рассмотреть другой язык, который состоит из соответствующих "выделенных частей" - там могут получиться разные странные особенности, но про это уже можно говорить. Т.е. если хотите, чтобы алгоритм "не пользовался" $w_2$ - рассмотрите язык, состоящий просто из слов $w_1$ (или добавьте такие слова в язык).
Но это нужно сделать до формулировки каких-то результатов. $P$ определяется как класс языков, которые распознаются за полиномиальное от размера входа время. Всё, любые опоры на "достаточную информацию" - это уже что-то другое, что нужно строго определить прежде чем обсуждать.

dmitgu в сообщении #1275100 писал(а):

я вообще-то рассматриваю в качестве "входной информации" для алгоритма и его собственный программный код

Отправной точкой является язык - просто множество слов. Затем для конкретного алгоритма там можно попробовать найти строку, содержащую код этого алгоритма.
Но язык, принадлежность которого к $NP \setminus P$ доказывается, должен быть конкретным, а не зависящим от алгоритма.

[dmitgu]

mihaild в сообщении #1275104 писал(а):

язык, принадлежность которого к $NP \setminus P$ доказывается, должен быть конкретным, а не зависящим от алгоритма.

Так и есть.

И как Вам насчёт этого:

dmitgu в сообщении #1275100 писал(а):

Если алгоритм не обращается к $w_2$, то его ответ не зависит от $w_2$ и относится к любому варианту этого $w_2$.

Тут не сработает подход:

mihaild в сообщении #1275104 писал(а):

Если "достаточная информация" легко выделяется из слова - то можно рассмотреть другой язык, который состоит из соответствующих "выделенных частей"

Потому что частью входной информации оказывается программный код алгоритма. И он получает его не в аргументах. Хоть в языке он и имеется в качестве части слова, но он-то не передаётся.

В общем, я понял, что для Вас важно формальное слово на входе, даже если оно в большей части и не должно использоваться алгоритмом. Я подумаю, как это совместить с практикой, когда такой "хвост" у программистов считается "мусором" и смысла в размере с учётом "мусора" нет. По мне, так даже если формализм и требует учёта "мусора" - то это дефект формализма. Но я подумаю, что тут и как - не сейчас, так как я этой "загвоздки" даже не предполагал, надо ещё привыкнуть, что есть и такой вопрос.

[mihaild]

dmitgu в сообщении #1275109 писал(а):

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

Совершенно непонятно, что это могло бы означать в терминах языка.

Можно, конечно, взять язык $L$ и рассматривать, как себя ведет алгоритм $T$ на слове $\overline{T}, x$ где $x \in L$. Но это какое-то странное и непонятно зачем нужное занятие.

Нужные определения мы с вами согласовали.

На практике бывают "легкие" примеры - например, если нам дана 3-КНФ, то уже первые 8 конъюнкций могут быть в совокупности невыполнимы, и оставшееся анализировать смысла нет. Но как правило интересно время работы в худшем случае.

Если что-то является "мусором" - ну рассмотрите язык, состоящий из слов, в которых этот "мусор" отрезан. Если при этом что-то ломается - вы скорее всего делаете что-то не то.

[dmitgu]

mihaild в сообщении #1274820 писал(а):

Перечитайте определение $P$. Время работы считается относительно входа, никакой "наиболее короткой информации" там нет.

Абзац с ответом на данную цитату ниже, выделен жирным шрифтом. Но сначала надо кое-что разобрать.

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

Формализм, определяющий слово, касается лишь того, что находится внутри данного слова, но он никак не определяет того, является ли данное слово частью другого слова, например, или нет.

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

Если теория (некий набор аксиом и выводимых из них теорем) содержит теорему о своей непротиворечивости, то она противоречива.

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

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

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

Действительно: в первом случае некоторые слова имеют внутреннее содержание (некое второе слово, строго внутри первого), а во втором – не имеют.

Ниже мы разберём, какие ещё существенные отличия между данными языками выводятся из способа выделения слов.

Разумеется, способ выделения слов не должен быть противоречивым - слово может выделяться любым способом, если он не противоречит иным способам выделения слова и проверки его принадлежности языку, которые уже заданы для данного языка.

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

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

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

Помимо сказанного, в интересующем нас случае «исключающее внутреннее слово» находится в начале «слова-контейнера». То есть, «слова-контейнеры» имеют вид:

$AX$

Где $A$ – «исключающее внутреннее слово», а $X$ – любое возможное продолжение, включая и отсутствие продолжения слова-контейнера.

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

При этом способ проверки на принадлежность языку «исключающего внутреннего слова» задан в нашем случае как базовый. А проверка для «слова-контейнера» - производная и совпадает с базовой проверкой «автоматически».

Классы языков, для которых проверка «исключающих внутренних слов» является базовой, можем обозначить так:

$I_{-e}$, где $e$ – список «исключающих внутренних слов».

Буква «e» от «исключение» – «exception», а буква «I» от «внутренний» – «internal». Дефис перед «e» - на случай расширения обозначения до $I_{w, -e}$, где $w$ – список «включающих внутренних слов».

Если же говорить об алгоритме проверки, который мог бы представлять язык таких классов (по аналогии с алгоритмами проверки для языков из классов $P$ или $NP$), то требования к ним такие:

Считывающая головка не должна считывать никакой входной информации о слове-контейнере после того, как выявлено «исключающее внутреннее слово». Время должно соответствовать тому, которое будет в случае, если вся информация о слове-контейнере представляет собой одно только данное «внутреннее слово».

Если данное требование НЕ выполнено, то тогда алгоритм проверки представляет не необходимый для представления язык с соответствующими «исключающими внутренними словами», а нечто другое.

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

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

И ответ на вопрос в начале этой заметки про $P$-алгоритм, который читает весь «вход» будет такой: подобный алгоритм не соответствует языку с «исключающими внутренними словами», потому что считывающая головка продолжает считывание и после того, как она прошла всё «исключающее внутренне слово». И такой $P$-алгоритм не представляет тот язык, который представляет исходный $NP$-алгоритм.

Теперь упомяну некоторые замеченные факты про «внутренние слова», которые выходят за рамки рассмотрения вопроса про $NP \ne P$.

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

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

Удивительно, что такая огромная практика до сих пор никак не учитывалась в формализме языков.

Каждое слово (обычное или в духе регулярных выражений) в заданном тексте – это отдельная задача по поиску и – в этом смысле – отдельный язык, о принадлежности к которому (можно найти искомое слово или нет) решается соответствующая задача поиска. Даже простое отдельное слово создаёт язык! И язык этот состоит из слов (текстов) в которых есть (а можно взять в качестве альтернативного построения языка условие «нет») данное слово.

И искомое слово выделяется алгоритмом поиска вовсе не из вакуума – его окружают символы другого слова, которое содержит искомое.

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

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

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

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

Не знаю, когда смогу продолжить общение тут – работы в этом году по 12-13 часов в день и выходные часов по 5. Написал эту заметку, чтобы хоть как-то двигаться в своём хобби. Прочитаю ответы (если кто ответит) и напишу, когда (и, если) будет время и силы.

[mihaild]

Совершенно непонятно, что такое "слова-контейнеры", "внутренние слова" и всё прочее.
Естественно что можно рассматривать языки, слова которых имеют какую-то "структуру" - этим занимается огромный раздел, называющийся "теория формальных языков". В частности, есть иерархия Хомского, описывающая, насколько "сложно" "задать структуру" языка.
И в теории сложности тоже как правило рассматривают задачи вида "проверить, удовлетворяет ли граф какому-то свойству" - при этом считается, что на вход подается корректное описание графа. Т.к. проверить, действительно ли данная строка описывает граф, несложно (если мы не стали изобретать очень странный способ описания графа), то на поведение алгоритма на словах, не являющихся описанием графа, внимания не обращают (при желании всегда можно договориться, что слова, не описывающие граф, языку не принадлежат, и добавить в начало проверку - во всех интересных задачах это как минимум не сложнее, чем проверить собственно интересующее нас свойство).

Вопрос о равенстве $P$ и $NP$ можно рассматривать как формализацию и уточнение простого и понятного практического вопроса - можно ли, например, быстро проверить $3-SAT$ формулу на выполнимость? Интересен этот вопрос тем, что есть много конкретных простых задач (примеры $NP$-полных задач), некоторые из которых важны для практики, про которые уже известно, что либо их все можно решить быстро, либо ни одну из них нельзя решить быстро.

Вы, конечно, можете пытаться сделать зачем-то свой формализм и в нем ставить и решать какие-то задачи. Но я бы советовал для начала как минимум разобраться в том, что уже придумали, и научиться четко формулировать свои определения и утверждения - иначе убедить разбирающихся людей хотя бы посмотреть на вашу работу будет очень сложно.

[Someone]

(dmitgu)

dmitgu в сообщении #1305422 писал(а):

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

Если теория (некий набор аксиом и выводимых из них теорем) содержит теорему о своей непротиворечивости, то она противоречива.

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

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

Прежде всего, нужно понимать, что арифметика Пеано говорит о натуральных числах и ни о чём другом. Любой "предмет", упоминаемый в арифметике Пеано, является натуральным числом, и ни о чём другом в арифметике говорить невозможно.
В частности, теорему о непротиворечивости арифметики в самой арифметике невозможно не только доказать, но даже и сформулировать. Потому что в этой теореме речь идёт о формулах арифметики и их доказательствах, которые вовсе не являются "предметами" арифметики. Они являются словами и последовательностями слов в языке арифметики, а не натуральными числами. Эта теорема — одна из метатеорем, которые формулируются и доказываются в так называемой метатеории.
Метатеория — это вспомогательная теория, которая используется для формализации арифметики (или другой формальной теории), то есть, для определения языка арифметики: нужно определить алфавит, термы, формулы, аксиомы, правила вывода и всё прочее, что нужно. Поэтому формулы и доказательства арифметики являются "предметами" метатеории, и в метатеории можно формулировать и доказывать метатеоремы об арифметике, в частности — непротиворечивость арифметики.
Собственно, Гёдель придумал способ закодировать метатеорему о непротиворечивости арифметики с помощью натуральных чисел и превратить её в утверждение о натуральных числах, которое уже можно сформулировать в языке арифметики. И это утверждение оказалось недоказуемым в арифметике. Но для арифметики это вовсе не утверждение о её собственной непротиворечивости, а просто утверждение о натуральных числах. Если не знать способа кодирования, то никак не догадаться, что это как-то связано с непротиворечивостью арифметики.

[dmitgu]

mihaild в сообщении #1305445 писал(а):

Совершенно непонятно, что такое "слова-контейнеры", "внутренние слова" и всё прочее.

Михаил, мы с Вами мыслим очень по-разному и тут приходится кропотливо разъяснять свою позицию – с обоих сторон, а каждый склонен «убегать» вперед и отвечать не на то, о чём говорит собеседник ) Я это понял, вроде, и стараюсь не спешить )

Смотрите, Вы рассматриваете слово как весь «вход». И, думаете, что это часть формализма. На этом построено Ваше возражение о размере слова для разбираемого $P$-алгоритма. Для меня это размер слова такого:

$\overline{Anti_{Sol, S}}, S, \overline{Sol(…, …, …)} $ (1)

А для Вас слово имеет такой вид (весь вход):

$\overline{Anti_{Sol, S}}, S, \overline{Sol(…, …, …)}, s$ (2)

(поправьте меня, если у меня не тот порядок частей слова, я уже забыл о каком мы условились)

Но – на каком основании Вы так считаете? Такой выбор слова (весь вход) вовсе не выводится из формализма слов. Это – Ваш произвол, пусть так «принято», но это же не доказано! И мой вариант слова (1) – тоже слово. И таков способ выделения слова в рамках построенного языка. Он – возможен и непротиворечив. Пусть «моё» слово обозначено $A$, а Ваше $AX$. Тогда:

До разбора слова $AX$, где $AX \ne A$, дело никогда не доходит. Всё заканчивается на слове $A$. Именно поэтому в языке нет и слова $AX$, где $AX \ne A$, а вовсе не потому, что его надо анализировать целиком для того, чтобы отвергнуть.

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

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

И, заметьте – уже по началу $A$ заведомо ясно, что никакой $AX$ принадлежать языку не будет. Поэтому $NP$-алгоритм его и не читает. И вдруг Вы хотите, чтобы $P$-алгоритм читал весь вход! На каком основании? А почему тогда не читать экспоненциально большое количество пустых клеток после окончания входа? Тогда любой язык $NP$ можно считать сводимым к $P$. Типа «не будем смотреть, какой размер использует $NP$-алгоритм, потому что он ошибается и там полно пустых символов». Чем пустые символы хуже «мусорных» не пустых? Ничем не хуже.

Заметьте, что когда Вы говорите, что $P$-алгоритм минимум линеен от длины входа, то Вы подменяете слова «максимум» на «минимум», потому что язык класса $P$ должен иметь алгоритм, который работает НЕ дольше, чем полиномиально от размера слова. НЕ дольше (а вовсе не минимум линеен). То есть – если он работает полиномиально от размера первых 5 символов входа – это тоже соответствует требованию к языку класса $P$.

Но, как оказалось, есть ещё и неучтённое в формализме – способ выделения слова. И если этот способ не соблюдается, то это – уже будет не тот язык. Если в исходном языке выделение слова при входе $AX$ всегда останавливается на $A$, то иное представление, которое читает слово AX целиком – заведомо не о том.

И Ваше возражение про размер слова оказывается поэтому ошибочным, а моё доказательство в вопросе размера слова (1) – обоснованным.

И о способах мышления – почему обсуждения у нас такие трудные:

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

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

[mihaild]

dmitgu в сообщении #1308719 писал(а):

И, думаете, что это часть формализма.

dmitgu в сообщении #1308719 писал(а):

Такой выбор слова (весь вход) вовсе не выводится из формализма слов. Это – Ваш произвол, пусть так «принято», но это же не доказано!

Это и не надо "доказывать", это часть определения.
Когда мы определяем МТ, мы фиксируем специальный символ $\#$, требуем, чтобы лента в начале имела вид "бесконечное влево число $\#$" + "строка, не содержащая $\#$" + "бесконечное вправо число $\#$". Ну или формально - у нас есть алфавит $A$, $# \in A$, ячейки ленты пронумерованы целыми числами, $f_t(x)$ - символ в ячейке номер $x$ в момент $t$. Существует такое $n$, что $f_0(x) \neq # \leftrightarrow 0 \leqslant x < n$. И это $n$ называется длиной входа, время работы оценивается именно по сравнению с ним.
Это всё часть стандартных определений, и когда говорят о P vs NP, подразумевают именно их.

(Оффтоп)

При этом оказывается, что разница во времени работы для разных "разумных" способов кодирования небольшая, поэтому о способе кодирования в задачах как правило явно не договариваются. Ну т.е. понятно, что граф из $n$ вершин можно как-то разумно описать строкой размера $O(n^3)$ так что можно будет отвечать на вопрос "есть ли ребро из $v$ в $w$" за полиномиальное от $n$ время. Дальнейшие уточнения важны только в вопросах, где умножение времени работы на полином кому-то интересно.

Если вы хотите предложить какие-то другие определения - ваше право. Правда при этом получится уже какой-то другой вопрос, и нужно либо доказать, что он эквивалентен стандартному, либо как-то объяснить, чем он интересен. Но перед этим - его четко сформулировать.

dmitgu в сообщении #1308719 писал(а):

я уже забыл о каком мы условились

post1256513.html#p1256513

dmitgu в сообщении #1308719 писал(а):

И таков способ выделения слова в рамках построенного языка. Он – возможен и непротиворечив.

Понятие "способ выделения слова" не определено.
И я, похоже, поторопился с фиксацией договоренностей. Надо было начинать с определения понятия "язык", "машина Тьюринга", "результат работы МТ на слове", "время работы" и т.д. Давайте для разнообразия определения этих понятий напишете вы?
(понятия "конечное множество", "натуральные числа", "целые числа", "функция" пока что для простоты считаем известными)

dmitgu в сообщении #1308719 писал(а):

И, заметьте – уже по началу $A$ заведомо ясно, что никакой $AX$ принадлежать языку не будет. Поэтому $NP$-алгоритм его и не читает.

(это замечание просто объясняет почему мне эти манипуляции с длиной слова кажутся очень странными, дальше развивать обсуждение сюда пока не надо)
Ну т.е. ваша МТ с подсказкой игнорирует вторую часть входа. Значит, в частности, для фиксированного $A$ все слова вида $AY$ не принадлежат языку (т.к. на принадлежащих языку словах такого вида ваша МТ ошибается, а ошибаться она не может). Ну так и рассмотрим сразу язык, получающийся из предыдущего отрезанием "ненужной" части.

dmitgu в сообщении #1308719 писал(а):

Заметьте, что когда Вы говорите, что $P$-алгоритм минимум линеен от длины входа, то Вы подменяете слова «максимум» на «минимум»

Нет, не подменяю. И для классического определения это так (т.к. требуется, чтобы в конце на ленте остался всего один символ). Но мы с вами уже договорились о другом определении $P$ (я с ним согласен, т.к. легко доказывается, что оно определяет в точности то же множество языков).

(Про формализм)

dmitgu в сообщении #1308719 писал(а):

Так общие усилия будут оптимальными, но надо терпеливее относиться к особенностям мышления друг друга

Ну это же вы пришли рассказывать решение сложной задачи какими-то странными методами, а не я:)
Я не понимаю, что вы пытаетесь сделать (ну точнее либо я не понимаю, либо вы пытаетесь сделать глупость, которая очевидно никаких результатов дать не может - я пока стараюсь верить в первый вариант). Формализм хорош тем, что это надежный способ передачи идей. Достаточно четко изложенную работу всегда можно проверить, и на практике почти всегда найдутся желающие это сделать.
Кроме того, формализация - это единственный известный мне надежный способ передачи идей. Т.е. я более-менее уверен, что если вы изложите свои мысли формально, то я либо смогу согласиться с ними, либо смогу найти в них ошибку, либо признаю что это что-то скорее всего осмысленное, но слишком сложное для меня, и тогда этим можно будет заинтересовать более умных чем я людей.

[dmitgu]

mihaild в сообщении #1308833 писал(а):

dmitgu: Такой выбор слова (весь вход) вовсе не выводится из формализма слов. Это -- Ваш произвол, пусть так «принято», но это же не доказано!

mihaild: Это и не надо "доказывать", это часть определения.
Когда мы определяем $МТ$, мы фиксируем специальный символ , …

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

В программировании это решается спец. обозначениями для спец. символов -- двухбуквенными, например (типа $\diagdown$n, $\diagdown$0 и т.п.). И рассматривается, фактически, некое подмножество языков, которое имеет отображение на всё их множество. А это не единственное необходимое обоснование. Например, как такое выделение слова (символом #) согласуется с другими способами выделения слова -- если они есть в языке.

Поэтому само по себе наличие протокола работы алгоритма не является определением, относящимся к языкам. Протокол может быть и не достаточно выразительным, чтобы представить некоторые языки. Протокол для $P$-алгоритма и оказывается неспособным представить $NP$-языки, если верно $NP \ne P$.

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

Но на самом деле, внутренняя структура у слова может быть. И в силу этого возникает неоднозначность в том, что должно подаваться на вход $P$-алгоритму:

1. произвольное слово, в котором алгоритм должен сам выделить нужное внутреннее слово при его наличии

2. или готовое «внутреннее слово», которое однозначно относит содержащее его слово (любое такое слово) к принадлежащим или не принадлежащим языку.

В случае, если на вход должно подаваться «внутреннее слово», получается, что $P$-алгоритм не представляет соответствующий язык, но интересующий нас результат будет тот же (как мы увидим). Оба варианта рассмотрим в обсуждении вопроса об «отрезании ненужной части» в словах и языке.

mihaild в сообщении #1308833 писал(а):

dmitgu: я уже забыл о каком мы условились

mihaild: post1256513.html#p1256513

Спасибо.

Вот там есть пункт про слова $\{1, 0\}^*$

И этот пункт -- про слово, но речь ведь идет только о внутреннем содержании слова. Ничто не мешает такому способу выделения слова $A$, которое обнаружит его в слове вида $AX$. И это тоже будет слово, соответствующее $\{1, 0\}^*$. Разумеется, важно, чтобы при этом не возникло противоречия с прочим содержанием в определении языка. Например:

Отвергаемое слово $A$ в языке, где слово $AX$ не имеет внутренней структуры (нет способа выделения исключающего внутреннего слова $A$) может относиться и к языкам, где некоторые $AZ$ принадлежат языку, а некоторые $AY$ не принадлежат. Но вот если у слов вида $AX$ есть внутренняя структура вида $A$ (способ выделения слова завершает работу, обнаружив $A$) и слово $A$ -- отвергаемое, то слова вида $AX$ могут относиться только к тем языкам, в которых никакое слово $AX$ словом языка не является.

Поэтому слова $AX$ с «исключающим внутренним словом» $A$ и без него -- разные слова. Но эти разные слова не могут быть в одном языке, потому что между словами $AX$ из одинаковых упорядоченных символов нет отличий -- просто в одном языке к слову привязано наличие внутренней структуры, а в другом -- отсутствие. Это как прямые и аксиома параллельных: Либо мы используем аксиому параллельных Евклида, либо используем одну из неевклидовых аксиом. Но не оба варианта сразу.

Кстати, на практике мы почти всегда имеем дело с языками, где слова обладают внутренней структурой.

mihaild в сообщении #1308833 писал(а):

И я, похоже, поторопился с фиксацией договоренностей.

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

mihaild в сообщении #1308833 писал(а):

Ну так и рассмотрим сразу язык, получающийся из предыдущего отрезанием "ненужной" части.

Сомневаюсь, что это возможно. Потому что для анализа системы (формализма, например) надо выйти за рамки системы, тем более, если к системе есть какие-то претензии. Например:

Если считать, что «вход» для $P$-алгоритма -- это как раз «значимая» часть слова (исключающее внутреннее слово), то получается интересный фокус -- для алгоритма-решения $Sol$ останется слово вида:

$\overline{Anti_{Sol, S}}, S, \overline{Sol(…, …, …)}$ (1)

Ведь в силу аксиомы рефлексии тут сразу ясно, что Sol не найдёт решения -- это следует из NP-алгоритма Ls. Поэтому часть s-малое отбрасывается. А вот для другого алгоритма (пусть NotSol) слово урезанным не будет и будет иметь вид:

$\overline{Anti_{Sol, S}}, S, \overline{Sol(…, …, …)}, s$ (2)

Тут-то и понятно, откуда возникает разница в работе $Sol$ и $NotSol$, если они соответствуют протоколу $P$: неполиномиальная разница в размере входа и корректный результат $0$ от $Sol$ создаст доказательство для $Anti_{Sol, S}$ (по построению $Anti_{Sol, S}$). Хотя… Тут надо сказать про «по построению $Anti_{Sol, S}$»:

Строили утверждение $Anti_{Sol, S}$ мы изначально для слова (1), дополненного частью $s = ss(S) $. Но в данный момент мы рассматриваем гипотетический случай «специфического» протокола для $P$-алгоритма -- когда часть $s$-малое для $P$-алгоритма $Sol$ не подаётся на «вход» («выбрасывается») и сразу после слова (1) стоит символ «#». Но и для такого «входа» мы легко (ещё легче!) проводим все необходимы построения для $Anti_{Sol, S}$, которые гарантируют, что $Sol$ в принципе не может предсказать правильный результат для этого утверждения. То есть -- какой бы протокол для $P$-алгоритма не был выбран (теперь он должен учитывать возможную внутреннюю структуру слова) -- он будет заранее известен и «под него» всегда можно построить соответствующее утверждение $Anti_{Sol, S}$.

Хотя, вариант протокола для $P$-алгоритма, в котором выбрасывается всё, кроме «исключающего внутреннего слова» представляется слишком искусственным и едва ли он будет принят -- на мой взгляд. Но с методической точки зрения он интересен:

В этом «специфическом» варианте протокола для $P$-алгоритма размер доказательства утверждения $Anti_{Sol, S}$ будет полиномиальным от размера «короткого» входа (1) при корректной работе алгоритма $Sol$. Полиномиальным он будет потому, что работа алгоритма $Sol$ с остановкой и результатом $0$ легко «перевести» в текст доказательства этого результата (а это и будет доказательство для $Anti_{Sol, S}$). При этом размер доказательства будет полиномиальным от времени работы алгоритма $Sol$. А время работы корректного $P$-алгоритма полиномиально от длины «входа» (тут «вход» - слово (1)). А это значит, что полученное доказательство для $Anti_{Sol, S}$ вполне укладывается в пределах размера входа (2) при достаточно больших $s = ss(S) $ и может быть найдено неким $NotSol$, по результату чего и будет выдано $1$ -- о принадлежности слова (2) языку $LS$, а вместе с ним и принадлежность языку $LS$ переданного в аргументах алгоритмe $NotSol$ слова:

$\overline{Anti_{Sol, S}}, S, s$ (3)

То есть, алгоритмы $Sol$ и $NotSol$ выдадут разные результаты и при этом алгоритм $Sol$ не сможет найти правильный результат для (3).

Но в «специфическом» протоколе работы слово (3) не будет передано алгоритму $Sol$ полностью -- из него будет выброшена $s$-малое. И, с одной стороны, с точки зрения слова (1) $s$-малое не требуется, потому что там есть часть от «аксиомы рефлексии», что позволяет заведомо знать (это есть в алгоритме $Ls$) о неспособности $Sol$ подтвердить утверждение $Anti_{Sol, S}$. Но, с другой стороны, слово (3) не имеет какого-то «исключающего внутреннего слова» внутри себя и «выбрасывать» $s$-малое для него -- неуместно. То есть «специфический» протокол создаёт два взаимоисключающих требования в данном случае, что ещё раз подтверждает, что его едва ли следует брать в качестве протокола для работы $P$-алгоритма.

Теперь вернёмся к «нормальному» протоколу работы $P$-алгоритма -- мы же имеем дело с теорией алгоритмов, где алгоритмы сами должны решать вопросы, а не получать «готовенькое» на вход. И в этом случае на вход должно подаваться то же, что и для $NP$-алгоритма $Ls$ (в части проверяемого слова). То есть -- слово (3) и для $Sol$. А слово (3) с учётом аксиомы рефлексии даст слово (1) плюс $s$-малое. Но, «способ выделения слова» при этом всё равно должен оставить лишь короткую часть (1) -- которая выделяется и используется $P$-алгоритмом $Sol$ из полученного на вход слова (2). И по факту получится то же самое (невозможность для $Sol$ выдать правильный результат для слова (3)), что только что было описано для «специфического» протокола работы $P$-алгоритма. А поскольку $Sol$ произволен, то это даёт $NP \ne P$.

Возможна ещё «придирка» в том, что хоть время работы $NP$-алгоритма $Ls$ у нас полиномиальна относительно размера слова $|A|$, но время работы $P$-алгоритма $Sol$ мы «имеем право» рассчитывать от размера слова $|AX|$. Потому что оба слова имеются на входе $NP$-алгоритма. Однако нас-то интересует полиномиальное преобразование от $NP$-языка к $P$-языку, а отличие между размерами $|A|$ и $|AX|$ - не полиномиальное, вообще говоря. Поэтому слово, от которого отсчитывается время работы, должно быть одним и тем же для $NP$-алгоритма и соответствующего ему $P$-алгоритма.

Однако, требование в предыдущем абзаце -- новое, строго говоря, потому что только сейчас выяснилась возможность выбирать между 2-мя разными словами.

Но, видимо, можно обойтись и без данного нового требования, а ограничиться первоначальным требованием формализма отвергать слово, не принадлежащее языку. В разбираемом случае этих слов два -- слово $AX$ и слово $A$. Если $P$-алгоритм проигнорировал слово $A$ и продолжил чтение слова $AX$, то тут явное игнорирование внутренней структуры слова, которое содержит внутри себя отвергаемое слово $A$ -- которое должно быть отвергнуто отдельно, то есть -- как только будет прочитано. Слово же $AX$ отвергается при этом «автоматически» - как частный случай любого $AX$, содержащего $A$ -- без необходимости его чтения целиком.

Конечно, в моих рассуждения используется ещё и «аксиома рефлексии» и «фактор содержания» (которые пришлось найти), зато видна вся «внутренняя кухня» (достаточно наглядно и просто, на мой взгляд) тех причин, по которым $NP \ne P$.

mihaild в сообщении #1308833 писал(а):

dmitgu: Заметьте, что когда Вы говорите, что $P$-алгоритм минимум линеен от длины входа, то Вы подменяете слова «максимум» на «минимум»

mihaild: Нет, не подменяю.

Возможно, мы думаем о разном, когда толкуем эти слова ) Я подразумевал лишь то, что даже если время работы полиномиально от первых пяти символов «входа» - оно всё равно соответствует протоколу работы для $P$-алгоритма. Потому что в соответствии с договорённостями post1256513.html#p1256513:

«время ее работы на входе x не превосходит $p(|x|)$»

И если время считается от $5$, то у нас есть ограничение, $p_2(5) = p(|x|)$ соответствующее требованию «не превосходит». И вместо $5$ мы можем брать и какие-то «короткие слова» в начале «входа» в качестве аргумента для полинома - всё равно протокол для $P$-алгоритма будет исполнен, если наш $P$-алгоритм уложиться в эти рамки полинома от размера «короткого внутреннего слова».

[mihaild]

dmitgu в сообщении #1310365 писал(а):

язык существует независимо от «представляющих» его алгоритмов.

Понятие "алгоритм представляет язык" не определено.

dmitgu в сообщении #1310365 писал(а):

Например, тот же символ «#» - как мы будем рассматривать языки, в которых слова содержат такой символ?

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

dmitgu в сообщении #1310365 писал(а):

Поэтому само по себе наличие протокола работы алгоритма не является определением, относящимся к языкам. Протокол может быть и не достаточно выразительным, чтобы представить некоторые языки. Протокол для $P$-алгоритма и оказывается неспособным представить $NP$-языки, если верно $NP \ne P$.

Термин "протокол алгоритма" (точнее "протокол машины Тьюринга") существует, но его стандартное определение не позволяет такого использования, как у вас.
Стандартное определение: путь $M$ - МТ. Тогда конечная или бесконечная последовательность троек вида (строка, целое число, состояние $M$) называется протоколом $M$ на входе $x$, если первый элемент этой последовательности - $(x, 0, S)$, следующий элемент получается из предыдущего через функцию перехода понятно как, и состояние из последней тройки (если последовательность конечная) - завершающее.

dmitgu в сообщении #1310365 писал(а):

под «словом» в математике сейчас принято понимать (хоть это и не следует из математического формализма!) слово без внутренней структуры

Определение. Словом длины $n$ в алфавите $A$ называется функция $f: \{1, 2, \ldots, n\} \to A$. $n$ в этом случае называется длиной слова, а $f(i)$ - $i$-м символом слова.
Непонятно, из какого формализма это должно следовать. Это базовое определение, на котором строится всё остальное.
Если хотите предложить другое - предлагайте. Только вам придется объяснить, зачем оно нужно.
Для задач типа "придумать простое отображение из множества графов во множество слов" этого определения вполне достаточно.

dmitgu в сообщении #1310365 писал(а):

речь ведь идет только о внутреннем содержании слова

Понятие "внутреннее содержание слова" не определено.

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

На всякий случай - стандартные определения.
Пусть $A$ - конечное множество (алфавит), $\# \notin A, A^\prime = A \cup \{\#\}$.
0. (Конечным) словом длины $n$ в алфавите $A$ называется функция $f: \{1, 2, \ldots, n\} \to A$.
1. Языком в алфавите $A$ называется произвольное множество слов в алфавите $A$.
2. МТ в алфавите $A$ с пробельным символом $\#$ - кортеж вида $(Q, A, #, S, F_0, F_1, \delta)$, где $Q$ - конечное "множество состояний" МТ, $S, F_0, F_1 \in Q$ - выделенные стартовое, принимающее и отвергающее состояния, $\delta: Q \setminus \{F_0, F_1\} \times A^\prime \to Q \times A^\prime \times \{L, N, R\}$ - в какое состояние переходит, что пишет и куда сдвигается головка МТ, прочитав в каком-то состояни какой-то символ.

Если по этим определениям вопросов нет - можно идти дальше.
(хотя лучше бы вы прочитали учебник, разобрались с определениями из него, спросили если что непонятно - переписывание учебника сюда вряд ли является сильно полезной деятельностью)

[dmitgu]

mihaild в сообщении #1310548 писал(а):

dmitgu в сообщении #1310365
писал(а):

Например, тот же символ «#» - как мы будем рассматривать языки, в которых слова содержат такой символ?

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

Вот, то есть - алгоритм и язык - это разные вещи и для достижения соответствия могут потребоваться какие-то специальные усилия. А в некоторых случаях никакие усилия не помогут. О том и пример про символ #.

mihaild в сообщении #1310548 писал(а):

Понятие "алгоритм представляет язык" не определено.

И напрасно. Я это "представляет" срисовал из логики. Там доказывается, что теория Пеано, например, "представляет" некие математические операции. Так как сама теория состоит из утверждений, то $2+2$ не могут дать $4$ - все эти числа не существуют "сами по себе", но можно построить предикат $F(a, b, c)$, такой что доказывается $F(2, 2, 4)$ и для остальных значений вместо $4$ будет доказано обратное, вроде: $\neg F(2, 2, 5)$. То есть - если алгоритм располагает информацией о слове, но не в состоянии обнаружить его и принять или отвергнуть - то он "не представляет" язык. И доказательство соответствия между алгоритмами, "работающими" со словами и языками, принимающими и отвергающими эти слова - необходимо. Потому что это - разные "конструкции".

mihaild в сообщении #1310548 писал(а):

На всякий случай - стандартные определения.
Пусть $A$ - конечное множество (алфавит), $\# \notin A, A^\prime = A \cup \{\#\}$.
0. (Конечным) словом длины $n$ в алфавите $A$ называется функция $f: \{1, 2, \ldots, n\} \to A$.
1. Языком в алфавите $A$ называется произвольное множество слов в алфавите $A$.

Прекрасно. Вот слово "Ёжик отправился в ночной лес на охоту" из символов русского алфавита и пробелов. При этом кусок "Ёжик отправился" - тоже слово - оно соответствует Вашему определению. И не имеет никакого значения, что справа от него в предложении стоит " в ночной лес на охоту". Вот о чём я, когда говорю, что определение слова зависит только от "внутреннего содержания". А не от того, что находится слева или справа от слова и где это слово - в Африке или на Луне. И если мы задаём пункт 1, то это никак не противоречит тому, что внутри слов языка могут быть другие слова языка. То же касается и "дополнительного языка" (ну, слова, которые отвергнуты).

Другое дело, что (не)принадлежность "внутреннего слова" не должна противоречить (не) принадлежности содержащего его слова. То есть - тут имеется неполнота, которая может быть расширена как внутренним содержанием для слова, так и отсутствием этого содержания. Притом что на практике внутреннее содержания у слова обычно есть.

Пример - язык из слов - грамматически правильные тексты из русских букв, пробелов и знаков пунктуации. Рассмотрим рассказ:

"Ёжик отправился в ночной блаблабла лес на охоту. <Дальше продолжение текста>". Данный текст будет отвергнут на практике как не соответствующий грамматике на первом же предложении. Потому что "внутреннее слово" с набором символов "блаблабла" не является грамматически правильным. А текст (любой), содержащий грамматически некорректный отрезок - тоже не является грамматически корректным. То есть, мы имеем практический пример языка с "исключающими внутренними словами".

mihaild в сообщении #1310548 писал(а):

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

Ок, я знаю, что зачастую увлекаюсь и забегаю вперед )

З.Ы. Я говорил и напоминаю, что не обещаю сейчас быстро отвечать, потому что много дел и на хобби не так часто остаются время и силы.

[mihaild]

dmitgu в сообщении #1311009 писал(а):

алгоритм и язык - это разные вещи

Ну да, это очевидно. Например, языков сильно больше, чем алгоритмов.

dmitgu в сообщении #1311009 писал(а):

и для достижения соответствия могут потребоваться какие-то специальные усилия

Непонятно, о каком "соответствии" речь. Мы вводим понятие "данная МТ распознает данный язык". И в процессе этого опеределения нам нужен символ не из языка. Ничего страшного, возьмем какой-нибудь, и докажем, что все интересные нам утверждения не зависят от того, какой именно символ выбрать (это в общем-то очевидно).

dmitgu в сообщении #1311009 писал(а):

И напрасно.

Ну так введите определение, если оно вам нужно. Маловероятно, что это кто-то сделает за вас.

dmitgu в сообщении #1311009 писал(а):

Так как сама теория состоит из утверждений, то $2+2$ не могут дать $4$

Первый раз вижу формулировку вида "(терм) не может дать (другой терм)", и не могу представить, что бы она могла означать.

dmitgu в сообщении #1311009 писал(а):

но можно построить предикат $F(a, b, c)$, такой что доказывается $F(2, 2, 4)$ и для остальных значений вместо $4$ будет доказано обратное, вроде: $\neg F(2, 2, 5)$

Только не предикат, а формулу. Ну можно, например $F(a, b, c) := << c = 4 >>.
(если занудствовать, то в арифметической сигнатуре нет симолов $2$ и $4$; но как их туда добавить - понятно)

dmitgu в сообщении #1311009 писал(а):

алгоритм располагает информацией о слове

dmitgu в сообщении #1311009 писал(а):

не в состоянии обнаружить его

Понятия "алгоритм располагает информацией" и "алгоритм не в состоянии обнаружить слово" не определены.

Мы так с вами никогда никуда не уедем. Давайте про каждое новое слово явно говорить, что оно значит - давать ему определение, используя только уже введенные слова.
Понятия "множества", "функция", "конечное множество" и им подобные считаем известными; при необходимости вернемся к их определениям.

dmitgu в сообщении #1311009 писал(а):

языками, принимающими и отвергающими эти слова

Языки принимают и отвергают слова???

dmitgu в сообщении #1311009 писал(а):

то это никак не противоречит тому, что внутри слов языка могут быть другие слова языка

Так, вы кажется говорите "слово содержит внутри другое слово", если второе слово является подстрокой первого.
На всякий случай - определение:
0.1. Пусть $f$ и $g$ - слова длины $n$ и $m$ в алфавите $A$, $m \leqslant n$. Слово $g$ называется подсловом (или подстрокой) слова $f$, если существует такое $k \leqslant n - m$, что $f(k) = g(1), f(k + 1) = g(2), \ldots, f(k + m - 1) = g(m)$.
Вы про это?

dmitgu в сообщении #1311009 писал(а):

Другое дело, что (не)принадлежность "внутреннего слова" не должна противоречить (не) принадлежности содержащего его слова.

Понятие "принадлежность чему-то там противоречит" не определено.