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

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

n,

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

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

-языки, если верно

.
Но. с другой стороны -- я не встречал явного требования, чтобы

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

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

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

-алгоритм не представляет соответствующий язык, но интересующий нас результат будет тот же (как мы увидим). Оба варианта рассмотрим в обсуждении вопроса об «отрезании ненужной части» в словах и языке.
dmitgu: я уже забыл о каком мы условились
mihaild: post1256513.html#p1256513
Спасибо.
Вот там есть пункт про слова

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

, которое обнаружит его в слове вида

. И это тоже будет слово, соответствующее

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

в языке, где слово

не имеет внутренней структуры (нет способа выделения исключающего внутреннего слова

) может относиться и к языкам, где некоторые

принадлежат языку, а некоторые

не принадлежат. Но вот если у слов вида

есть внутренняя структура вида

(способ выделения слова завершает работу, обнаружив

) и слово

-- отвергаемое, то слова вида

могут относиться только к тем языкам, в которых никакое слово

словом языка не является.
Поэтому слова

с «исключающим внутренним словом»

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

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

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

останется слово вида:

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

(2)
Тут-то и понятно, откуда возникает разница в работе

и

, если они соответствуют протоколу

: неполиномиальная разница в размере входа и корректный результат

от

создаст доказательство для

(по построению

). Хотя… Тут надо сказать про «по построению

»:
Строили утверждение

мы изначально для слова (1), дополненного частью

. Но в данный момент мы рассматриваем гипотетический случай «специфического» протокола для

-алгоритма -- когда часть

-малое для

-алгоритма

не подаётся на «вход» («выбрасывается») и сразу после слова (1) стоит символ «#». Но и для такого «входа» мы легко (ещё легче!) проводим все необходимы построения для

, которые гарантируют, что

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

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

.
Хотя, вариант протокола для

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

-алгоритма размер доказательства утверждения

будет полиномиальным от размера «короткого» входа (1) при корректной работе алгоритма

. Полиномиальным он будет потому, что работа алгоритма

с остановкой и результатом

легко «перевести» в текст доказательства этого результата (а это и будет доказательство для

). При этом размер доказательства будет полиномиальным от времени работы алгоритма

. А время работы корректного

-алгоритма полиномиально от длины «входа» (тут «вход» - слово (1)). А это значит, что полученное доказательство для

вполне укладывается в пределах размера входа (2) при достаточно больших

и может быть найдено неким

, по результату чего и будет выдано

-- о принадлежности слова (2) языку

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

переданного в аргументах алгоритмe

слова:

(3)
То есть, алгоритмы

и

выдадут разные результаты и при этом алгоритм

не сможет найти правильный результат для (3).
Но в «специфическом» протоколе работы слово (3) не будет передано алгоритму

полностью -- из него будет выброшена

-малое. И, с одной стороны, с точки зрения слова (1)

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

) о неспособности

подтвердить утверждение

. Но, с другой стороны, слово (3) не имеет какого-то «исключающего внутреннего слова» внутри себя и «выбрасывать»

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

-алгоритма.
Теперь вернёмся к «нормальному» протоколу работы

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

-алгоритма

(в части проверяемого слова). То есть -- слово (3) и для

. А слово (3) с учётом аксиомы рефлексии даст слово (1) плюс

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

-алгоритмом

из полученного на вход слова (2). И по факту получится то же самое (невозможность для

выдать правильный результат для слова (3)), что только что было описано для «специфического» протокола работы

-алгоритма. А поскольку

произволен, то это даёт

.
Возможна ещё «придирка» в том, что хоть время работы

-алгоритма

у нас полиномиальна относительно размера слова

, но время работы

-алгоритма

мы «имеем право» рассчитывать от размера слова

. Потому что оба слова имеются на входе

-алгоритма. Однако нас-то интересует полиномиальное преобразование от

-языка к

-языку, а отличие между размерами

и

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

-алгоритма и соответствующего ему

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

и слово

. Если

-алгоритм проигнорировал слово

и продолжил чтение слова

, то тут явное игнорирование внутренней структуры слова, которое содержит внутри себя отвергаемое слово

-- которое должно быть отвергнуто отдельно, то есть -- как только будет прочитано. Слово же

отвергается при этом «автоматически» - как частный случай любого

, содержащего

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

.
dmitgu: Заметьте, что когда Вы говорите, что

-алгоритм минимум линеен от длины входа, то Вы подменяете слова «максимум» на «минимум»
mihaild: Нет, не подменяю.
Возможно, мы думаем о разном, когда толкуем эти слова ) Я подразумевал лишь то, что даже если время работы полиномиально от первых пяти символов «входа» - оно всё равно соответствует протоколу работы для

-алгоритма. Потому что в соответствии с договорённостями post1256513.html#p1256513:
«время ее работы на входе x не превосходит

»
И если время считается от

, то у нас есть ограничение,

соответствующее требованию «не превосходит». И вместо

мы можем брать и какие-то «короткие слова» в начале «входа» в качестве аргумента для полинома - всё равно протокол для

-алгоритма будет исполнен, если наш

-алгоритм уложиться в эти рамки полинома от размера «короткого внутреннего слова».