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

[dmitgu]

Someone в сообщении #1322475 писал(а):

dmitgu в сообщении #1322472

писал(а):
Для $PA$? Да, для PA первого порядка. В соответствии с вашими словами: dmitgu в сообщении #1322458

писал(а):
Доказательство не категоричности теорий 1-го порядка для арифметики … А теперь Вы почему-то начали ссылаться на теории второго порядка: dmitgu в сообщении #1322472

писал(а):
Оно начинается с предложения второго порядка, которое имеет только несчётные интерпретации. А аксиома индукции 2-го порядка - это практически отрицание данного предложения.

Так я и сравнивал отличия! Для 1-го порядка несчётная интерпретация есть, а для второго - нет. Это разные вещи ))))

Someone в сообщении #1322475 писал(а):

Это общепринятая формализация. dmitgu в сообщении #1322472

писал(а):
И мы после уточняли, что нумерация не фиксированная Это — несущественное расширение. Оно легко элиминируется.

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

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

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

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

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

У Бурбаки например наверняка есть какая-то (совершенно неудобоваримая) запись для этого.

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

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

Вполне соответствует - из вашего "слова" (и вообще из любой структуры, позволяющей брать длину и $i$-й символ) легко изготавливается отображение из начального отрезка натурального ряда в алфавит.

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

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

чего при определении фундаментальных понятий делать не хотелось бы

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

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

dmitgu в сообщении #1322458

писал(а):
Кстати, как Вы видели выше, для теории первична интерпретация Нет, не видел.
Ну и понятие "первичность" не определено.

Ну, в интерпретации ведь уже расставлены все истинности, а теория - это такой "сжатый вариант". Вот имея некую реальную картину мы имеем понимание о свойствах ("истинности" расставлены) и придумываем нашу теорию в соответствии с интерпретацией.

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

dmitgu в сообщении #1322458

писал(а):
да и заведомо нельзя дать такое определение на базе теории 1-го порядка Да ладно? Почти вся математика живет в первом порядке, и прекрасно себя чувствует.

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

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

Ладно, раз вы называете цитируемые мной по памяти определения "придуманными мной" - давайте брать определения с ProofWiki.
(или можете предложить любую другую коллекцию схожего объема, приведенную в более-менее консистентный вид)
ProofWiki в Definitin:Sequence

писал(а):
A sequence is a mapping whose domain is a subset of natural numbers \mathbb{N}.
(кстати тут они согласны с вашим вариантом - "дырки" в нумерации разрешены)
ProofWiki в Definitin:String

писал(а):
Let $A$ be an alphabet of symbols. A string (in $A$) is a sequence of symbols from $A$.

Ну, теперь мы уже по английски будем писать для большей непонятности))))

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

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

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

В общем, Вы согласны с тем, что строка и подстрока (сплошная) - это слово? В Вашем "определении" словом окажется не только сплошная подстрока, но и набор символов через один )) Соглашайтесь ))

[mihaild]

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

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

Приведите цитаты, пожалуйста.

Я предлагал определение "слово - функция из начального отрезка натурального ряда в алфавит". Это одно из возможных определений (и, кажется, самое распространенное). Можно придумать много других, несущественно от него отличающихся.
Как только вы сформулировали что-то, похожее на определение, разрешающее пропуски, я согласился, что так тоже можно.

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

Можно называть типа-словом функцию из какого-то конечного подмножества натуральных чисел в алфавит. Такое определение вас устроит?

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

Если Вы даете определение слова, то оно должно допускать все варианты слова.

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

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

Любое подмножество (даже и не сплошное) тоже оказывается слово - так как порядок задаётся нумератором.

Ну да. Вот у нас сеть слово $abcde$. А есть слово $abe$.

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

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

это ведь определение на основании объектов со сложностью второго порядка

Что такое "сложность второго порядка"?
Нет, определение "отображение из начального отрезка натурального ряда в алфавит" - это определение в ZF. Которая является теорией первого порядка.

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

а как избавится от "глобальной упорядоченности" - когда подммножество (не сплошное) - тоже слово?

Никак. А зачем от нее избавляться?
Просто заводим два отдельных термина: "вхождение как подстроки" и "вхождение как подпоследовательности".

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

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

Хорошо, могу перевести.
Последовательность - это отображение, доменом которого является подмножество $\mathbb{N}$.
Строка в алфавите $A$ - это последовательность элементов $A$.

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

В общем, Вы согласны с тем, что строка и подстрока (сплошная) - это слово?

Вообще обычно подстрока определяется как "строка, такая что ...". И подстрока автоматически является строкой. И подпоследовательность строки тоже является строкой.

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

Не проще ли написать теорию первого порядка и покончить с секретностью?

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

[dmitgu]

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

dmitgu в сообщении #1322504

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

Легко:

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

mihaild в сообщении #1315425

писал(а):
Что значит "нумерация" в данном случае?

Я вообще не очень понимаю, о чем спор. "Слово в алфавите $A$" - это просто другое название "функции в из $\{0, \ldots, n\}$ в $A$". Всё, что не является такой функцией, не является словом. Просто по определению.
Ёлки, кажется, я Вас понял. Вы считаете, что есть фиксированная нумерация? Когда символу жёстко приписан номер. И поэтому её (нумерацию) нельзя менять. Но это же ошибка. Вот смотрите:...

и затем Вы соглашаетесь поменять свою позицию:

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

dmitgu в сообщении #1315899

писал(а):
Никакой разницы!
Как это никакой - это два разных множества.
Можно, конечно, ввести (понятно какое) отношение эквивалентности на них, но опять же нужно это явно сделать.

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

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

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

А почему Вы так боитесь теории первого порядка? Сколько уже недель определение составить не получается (я в этом не участвую :), а теорию я сделал моментально. Так надо использовать то, что простое, эффективное и работает, а не неведомо что :) В конце концов и определение и теория первого порядка задают свойства. Какая разница? Проще ведь не будет с Вашим определением - если вдруг даже Вы его и придумаете. И это будет что-то ну очень сложное. Плюс все свойства, которые у меня в аксиомах. Чего ради добавлять что-то сверх них?

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

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

Да какие уж там "вершины", выбраться бы из тупика, из которого Вы выходить не хотите, хоть и не заперты ))

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

и любая подпоследовательность слова - это тоже слово. Из стандартных определений это легко выводится.

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

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

Никак. А зачем от нее избавляться?
Просто заводим два отдельных термина: "вхождение как подстроки" и "вхождение как подпоследовательности".

Сказанное только что повторяю и тут )

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

Вообще обычно подстрока определяется как "строка, такая что ...". И подстрока автоматически является строкой. И подпоследовательность строки тоже является строкой.

Вот, а в середине декабря прошлого года Вы не соглашались, что во входном слове есть и другие слова ))

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

Последовательность - это отображение, доменом которого является подмножество $\mathbb{N}$.

Ага, всё=таки не от 1 до N (длины строки) :) Но всё равно ошибочное, как отмечено выше.

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

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

Да, но не все свойства, которые выводятся из Вашего (а вовсе не стандартного) определения являются свойствами некоторых слов.

Ладно, в целом достигнут принципиальный прогресс по подстрокам, которые теперь признаны словами. Сформулировали расхождения в некоторых основах - тоже хорошо. Можно, наверно возвращаться к завершение доказательства, но надо работать - может в конце недели доберусь до хобби. И спасибо за обсуждение!

[Someone]

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

Так я и сравнивал отличия! Для 1-го порядка несчётная интерпретация есть, а для второго - нет. Это разные вещи ))))

Это я знаю. Но абзац, который мы обсуждали, не содержит никаких упоминаний теорий второго порядка:

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

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

Если что — арифметика Пеано 1-го порядка обсуждается и исследуется гораздо больше, чем соответствующая теория 2-го порядка.

[mihaild]

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

и затем Вы соглашаетесь поменять свою позицию

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

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

А почему Вы себя ставите в такое выделенное положение?

Потому что 1) это вы приходите с просьбой проверить ваш результат, а не наоборот; 2) потому что я считаю, что именно эти определения (с точностью до несущественных отличий) даст любой профессиональный математик, если его спросить. Someone уже подтвердил, можете спросить еще кого-то из умных людей на форуме. Можете посмотреть ProofWiki (или книги, на которые она ссылается). Можете, наконец, написать в инстутут Клея: "ваше описание неполное, используется термин string, но нигде не написано, что он значит; напишите, пожалуйста" - скорее всего, вам дадут ссылку на какой-нибудь источник, где написано примерно то определение, которое я привел.

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

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

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

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

Ваше - пока что не соответствует.

Нет, соответствует.

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

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

Либо врёте, либо ошибаетесь. Определение я вам привел сразу, и пока никаких принципиальных недостатков в нем не указано.

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

А почему Вы так боитесь теории первого порядка?

Потому что непонятно, зачем нужно плодить лишние сущности.

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

никто набор символов через один, выдернутых из строки не считает строкой

Вот строка $abcde$. Покажите мне человека, который $ace$ не считает строкой.

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

Вы не соглашались, что во входном слове есть и другие слова

Опять либо врёте, либо ошибаетесь. Я писал

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

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

Ну и что-то подобное.
Кстати, если фраза "$x$ - внутреннее подслово слова $y$" означает что-то кроме "$x$ - подстрока $y$" - то я всё еще не понимаю, что.

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

Да, но не все свойства, которые выводятся из Вашего (а вовсе не стандартного) определения являются свойствами некоторых слов

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

-- 25.06.2018, 20:45 --

И вообще, не хотите явно вводить индексацию - давайте назовем словами над $A$ элементы свободного моноида, порожденного $A$. Стало легче?

[dmitgu]

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

dmitgu в сообщении #1322514 писал(а):
Вы не соглашались, что во входном слове есть и другие слова

Опять либо врёте, либо ошибаетесь. Я писал

mihaild в сообщении #1310548 писал(а):
Понятие "внутреннее содержание слова" не определено.

Ну и что-то подобное.

Почитал дискуссию с декабря 2017 г.

Не сразу вспомнил, почему про весь вход – слово $(w_1, w_2)$ – я не упоминал в декабре 2017, что разбираемый $NP$-алгоритм в спец. случае зависит только от $w_1$ и время его работы полиномиально от размера $|w_1|$. Затем вспомнил, что это как раз из-за спора о возможности выделить из слова $ (w_1, w_2) $ его «внутренние слова». И если вопрос о «внутренних словах» стоял для $P$-алгоритма, то он так же стоял и для $NP$-алгоритма. И полиномиальность относительно размера $|w_1|$ будет и полиномиальностью относительно размера $|(w_1, w_2)| $ и про слово $w_1$ тогда и говорить нечего, если не доказано, что это именно слово – что его можно считать словом.

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

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

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

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

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

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

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

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

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

То есть, опять не я, а Вы «врете или ошибаетесь» вот тут:

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

dmitgu в сообщении #1322514 писал(а):
Сколько уже недель определение составить не получается

Либо врёте, либо ошибаетесь.
Определение я вам привел сразу, и пока никаких принципиальных недостатков в нем не указано.

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

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

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

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

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

dmitgu в сообщении #1322514 писал(а):
никто набор символов через один, выдернутых из строки не считает строкой

Вот строка $abcde$. Покажите мне человека, который $ace$ не считает строкой.

Это отличный пример для разбора и опровержения Вашего «определения». Смотрите – Вы с таким же успехом могли бы написать «Покажите мне человека, который $\text{«fgk»}$ не считает строкой». Какое отношение Ваше предложение имеет к строке $\text{«abcde»}$? Никакого.

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

А теперь скажите-ка мне, нормальные люди (те же программисты) согласятся, что внутри строки $\text{«abcde»}$ можно найти строку $\text{«ace»}$? Нет. Потому что её там нет. Потому что правильный ответ такой: $find(\text{«abcde»}, \text{«ace»}) = 0$.

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

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

чего при определении фундаментальных понятий делать не хотелось бы).

Неужели Вы думаете, что Вас вместе с любым количеством «профессионалов» не вынудят принять для слов (строк!) теорию с $find(\text{«abcde»}, \text{«ace»}) = 0$? Вынудят, даже не сомневайтесь )

Что касается желаний – то это непригодный метод для стандартизации (определений, аксиом и т.п.), потому что у каждого свои желания.

Поэтому в основе стандартов, как правило, лежит нечто объективное – в частности, конкретные практические задачи могут выступать в таком качестве. Я бы сказал ещё «творение Божие», но Вы атеист, наверное, и тут наши исходные посылки несовместимы.

А конкретно в отношении слов и языков источник вопросов (и про $NP \ne P$ тоже) – потребности криптографии. А это – программистские стандарты операций со строками, подстроками и тому подобным. Вот из этого и следует исходить.

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

И вообще, не хотите явно вводить индексацию - давайте назовем словами над $A$ элементы свободного моноида, порожденного $A$. Стало легче?

Так я уже сделал этот Ваш «моноид» - почитайте аксиомы моей теории страницей раньше. Наконец-то Вы со мной согласились )))

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

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

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

Можете, наконец, написать в инстутут Клея: "ваше описание неполное, используется термин string, но нигде не написано, что он значит

Да всё написано в сформулированных мной аксиомах ) Или в институте Клея тоже - противники аксиоматизации? ))

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

Кстати, если фраза "$x$ - внутреннее подслово слова $y$" означает что-то кроме "$x$ - подстрока $y$" - то я всё еще не понимаю, что.

Всё правильно – только подстрока и никаких подпоследовательностей. Наконец-то я Вам что-то объяснил ))

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

dmitgu в сообщении #1322514 писал(а):
Да, но не все свойства, которые выводятся из Вашего (а вовсе не стандартного) определения являются свойствами некоторых слов

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

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

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

dmitgu в сообщении #1322514 писал(а):
А почему Вы так боитесь теории первого порядка?

Потому что непонятно, зачем нужно плодить лишние сущности.

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

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

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

Я снова (через надцать лет) прочитал поверхностно аксиомы теории множеств NBG («Введение в математическую логику», Э. Мендельсон, Глава 4 «Аксиоматическая теория множеств», раздел 1 «Система аксиом») и не нашёл ничего, что могло бы быть формализацией для создания нужного класса эквивалентности.

Есть определения для пустого множества и множества двух множеств и т.п. определения, но – на основе аксиом. И есть специальная теорема в логике, которая доказывает, что введение таких определений не добавляет в теорию ничего существенного. Иначе это были бы, фактически – аксиомы. Ссылка на данную теорему стоит в упомянутом чуть выше Разделе 1 сразу после определений для пустого множества и множества для пары классов $\{X, Y\}$. А сами эти определения – после «Аксиомы N» для пустого множества.

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

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

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

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

Таким образом, никакой теории первого порядка с определением для слов у нас не было, и нет. Есть моя теория первого порядка для слов – что давно надо было сделать профессионалам, но сделано дилетантом мной ) И хватит защищать корпоративную «чистоту мундира», Михаил – она тут не защитима. Профессионалы в данном случае лопухнулись, а дилетант рулит ) Это я, Я, Я! ))))

Хоть я и не юрист Ферма и не телеграфист Хевисайт, но уверенным шагом иду в их направлении )))

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

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

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

Давайте напишем аксиомы, что ли ) ...

И немного подправлены тут (и Вы там одну аксиому упростили, кстати):

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

Я заметил, что кое-что прозевал. Вот такие исправленные аксиомы нужны: ...

Считаем, что:

0. $I_{ChrLim} > 0$ – у наc не унарный алфавит, но есть хотя бы «азбука Морзе» и возможность записи тех же чисел позиционным способом.

Доказывать будем

$Str( ChrStr(0) \cdot ChrStr(1), 2, 1 ) = ChrStr(1)$

Использовать будем аксиомы

1. $a = b \Leftrightarrow \forall i: str(a, i, 1) = str(b, i, 1)$, что такое равенство слов

2. $str(a, i, 1) = \emptyset \Rightarrow str(a, i + 1, 1) = \emptyset$, что такое конец слова (если он есть)

$( \exists len(a) ) \Rightarrow$

$( \exists c = a \cdot b )$

$\wedge ( i \le len(a) \Rightarrow str(c, i, 1) = str(a, i, 1) )$

$\wedge ( i > len(a) \Rightarrow str(c, i, 1) = str(b, i - len(a), 1) )$
- 2-я Аксиома конкатенации, а раз будем рассматривать конечные слова, то сократим её до такого вида:

$( \exists c = a \cdot b )$

$\wedge ( i \le len(a) \Rightarrow str(c, i, 1) = str(a, i, 1) )$

$\wedge ( i > len(a) \Rightarrow str(c, i, 1) = str(b, i - len(a), 1) )$

И нас не будет интересовать член конъюнкции с $i \le len(a)$, поэтому сократим до:

3. $( \exists c = a \cdot b ) \wedge ( i > len(a) \Rightarrow str(c, i, 1) = str(b, i - len(a), 1) )$

Понятно, что сделанные сокращения используют правило вывода $MP$ и тавтологии – например

$A \wedge B \Rightarrow B$. Если надо, я могу всё расписать, включая вывод тавтологий.

4. $\exists I_{ChrLim}:$

$( \forall i > I_{ChrLim}: ChrStr(i) = \emptyset )$

$\wedge ( \forall i \le I_{ChrLim} \forall j \le I_{ChrLim}: i = j \Leftrightarrow ChrStr(i) = ChrStr(j) )$

$\wedge ( \forall i \le I_{ChrLim}: ChrStr(i) = Str(ChrStr(i), 1, 1) \wedge Str(ChrStr(i), 2, 1) = \emptyset )$
- Аксиома для символов

Доказательство (вывод)

Перепишем 3 для $a = ChrStr(0) $, $b = ChrStr(1) $, при этом $len(a) = 1$ из определения $len()$. Получим

5. $\exists c: (c = ChrStr(0) \cdot ChrStr(1) ) \wedge ( i > 1 \Rightarrow str(c, i, 1) = str(ChrStr(1), i - 1, 1) )$

Подставим вместо $i$ число $2$ и уберем истинную посылку $2 > 1$ (не расписываю тавтологии, логический вывод, но приведу их – неохотно и не сразу :), если кому надо – так как работа с определением неравенства и его использование в выводе из Пеано потребует много шагов). Получим:

6. $\exists c: c = ChrStr(0) \cdot ChrStr(1) \wedge str(c, 2, 1) = str(ChrStr(1), 1, 1)$

В силу равенства $c = ChrStr(0) \cdot ChrStr(1) $ подставим вместо $c$ внутри $str()$ в 6 (технику вывода для «влезания» под квантор существования покажу ниже в пункте 9). Получим:

7. $\exists c: c = ChrStr(0) \cdot ChrStr(1) \wedge str(ChrStr(0) \cdot ChrStr(1), 2, 1) = str(ChrStr(1), 1, 1)$

Из тавтологии $A \wedge B \Rightarrow B$ получим:

8. $c = ChrStr(0) \cdot ChrStr(1) \wedge str(ChrStr(0) \cdot ChrStr(1), 2, 1) = str(ChrStr(1), 1, 1) \Rightarrow$

$str(ChrStr(0) \cdot ChrStr(1), 2, 1) = str(ChrStr(1), 1, 1) $

Из правила вывода для квантора существования (из «Оснований математики» Гильберта и Бернайса) и 8 получим:

9. $\exists c: c = ChrStr(0) \cdot ChrStr(1) \wedge str(ChrStr(0) \cdot ChrStr(1), 2, 1) = str(ChrStr(1), 1, 1) \Rightarrow$

$str(ChrStr(0) \cdot ChrStr(1), 2, 1) = str(ChrStr(1), 1, 1) $, это пример, как переносить результаты из логики высказываний под квантор существования.

Из 7 и 9 по правилу MP получим:

10. $str(ChrStr(0) \cdot ChrStr(1), 2, 1) = str(ChrStr(1), 1, 1)$

А из пунктов 0 и 4 получаем $ChrStr(i) = Str(ChrStr(i), 1, 1)$ – см. последнюю строку в пункте 4, вывод утверждения методом подстановок и извлечения одного утверждения из конъюнкции утверждений пропускаю. Итак:

11. $ChrStr(i) = Str(ChrStr(i), 1, 1) $

И из 10 и 11 и из $i=1$ получаем:

12. $str(ChrStr(0) \cdot ChrStr(1), i, 1) = ChrStr(1) $

Что и требовалось доказать. Я облегчил себе задачу из-за того, что выбрал строку из одного символа. Иначе пришлось бы использовать пункт 2 и доказывать равенство строк по индукции. Но и там принципиальных трудностей нет.

Очевидно, что искомая строка $ChrStr(i)$ будет найдена и функцией $find$ в строке $ChrStr(0) \cdot ChrStr(1)$ (см. соответствующую аксиому) и что верно неравенство $ChrStr(0) \cdot ChrStr(1) \ne ChrStr(i)$ – см. аксиому для равенства строк. Но, если нужны соответствующие выводы для доказательства этого – я тоже их приведу.

Вот примерно такой вывод, как представлен выше, я жду и от Михаила Д, чтобы увидеть, что у него (и сотен миллиардов профессионалов по всему миру :)) есть соответствующая теория первого порядка.

У меня сейчас отчётный период, поэтому не гарантирую ответов в июле. Всё же просьба – не использовать всякие «Ерунда», «Врёте или ошибаетесь» и т.п. Тем более, что «ерунда» и «враньё или ошибка» обычно не у меня )

[dmitgu]

Someone в сообщении #1322516 писал(а):

Если что — арифметика Пеано 1-го порядка обсуждается и исследуется гораздо больше, чем соответствующая теория 2-го порядка.

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

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

это вы приходите с просьбой проверить ваш результат, а не наоборот

Я думал, что прихожу как ёжик к медвежонку «считать звёзды», или встречу пёсика, который найдёт мой узелок с малиновым вареньем ) А вдруг вместо этого в тумане сова и летучая мышь – «Врёте или ошибаетесь» и «Ерунда». Жуть какая! )) Помните они там («Ёжик в тумане») вместе возникли, и ёжик даже испугался и побежал, и свалился в реку? Будьте как пёсик и медвежонок (или светлячок и кто-то в реке), а не как сова и летучая мышь ))))

[mihaild]

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

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

Будет. Просто подстрока в этом определении не является ограничением исходной функции, а сдвигом этого ограничения.
Например, у нас есть строка $abcd$ - это функция $f: \{1,2,3,4\} \to \{a,b,c,d,e,\ldots,z\} =: A, f(1) = a, f(2) = b, f(3) = c, f(4) = d$. Его подстрокой длины $2$, начинающейся со второго символа, будет не функция $g: \{2,3\} \to A$, а функция $g: \{1,2\}\to A, g(1) = b, g(2) = c$.

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

ошибочное суждение

Какое "суждение"? Я привел определения, все известные мне интересные утверждения про языки верны при таком определении слова.
И определения не бывают правильными и неправильными, они бывают общепринятыми и не общепринятыми. И общепринятость как раз определяется "голосованием" (специалистов). Естественно что любой желающий может вводить те определения, которые ему хочется. Но если этот желающий претендует на решение какого-то известного вопроса, то ему нужно в постановке этого вопроса пользоваться как раз стандартными определениями, а не вводить свои, им не эквивалентные.
Более точно, чтобы получить миллион от института Клея, нужно решить вопрос о равенстве $P$ и $NP$ именно в стандартных определениях, а не в других, "более соответствующих практике по чьему-то мнению".

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

А теперь скажите-ка мне, нормальные люди (те же программисты) согласятся, что внутри строки $\text{«abcde»}$ можно найти строку $\text{«ace»}$?

Еще раз. Есть два разных термина - подстрока и подпоследовательность. Если $x$ - подстрока $y$, то $x$ - подпоследовательность $y$, обратное в общем случае неверно. Например, $bc$ является подстрокой и подпоследовательностью $abcd$. $ac$ является подпоследовательностью, но не подстрокой $abcd$.
И никакой путаницы тут нет, про разницу между подстроками и подпоследовательностями знают и математики, и программисты, и вообще все, кто хоть немного интересовался вопросом. Если вы хотите ввести новый термин "внутреннее слово" как синоним "подстроки" - ну вводите (хотя и не очень понятно, зачем).

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

Одна из задач стандартизации основ – это максимальная понятность для наибольшего круга пользователей

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

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

почитайте аксиомы моей теории страницей раньше

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

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

Тоже люди будут по много месяцев спорить невесть о чём? Поэтому и нужна стандартизация.

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

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

$Str( ChrStr(0) \cdot ChrStr(1), 2, 1 ) = ChrStr(1)$

Если я правильно понимаю ваши обозначения, это значит "подстрока строки (получающеся конкатенацией строк $0$ и $1$) длины $1$, начинающаяся со второго символа, равна строке $1$".
Обозначения: $f = \{\langle 1, 0\rangle\}, g=\{\langle 1, 1\rangle\}, h = \{\langle 1, 0\rangle, \langle 2, 1\rangle\}, p=\{\langle 1, 1\rangle\}$.
Надо доказать: $\max\{x: \exists y: \langle x, y\rangle \in f\} = 1$, $\max\{x: \exists y: \langle x, y\rangle \in g\} = 1$ [длины $f$ и $g$ равны $1$]
$\forall i \in \{1\}: f(i) = h(i)$, $\forall i \in \{1\}: g(i) = h(i + 1)$, $\max\{x: \exists y: \langle x, y\rangle \in h\} = 1+1$ [т.е. $h$ - конкатенация $f$ и $g$]
$\max\{x: \exists y: \langle x, y\rangle \in p\} = 1$, $\forall i \in \{1\}: p(i) = h(i + 1)$ [$p$ - подстрока $h$ длины $1$, начинающаяся со второго символа]
Очевидно, что все эти утверждения можно доказать в ZF. Очевидно, что полностью формальных выводов в ZF я выписывать не буду (для этого есть автоматические системы, но я ими, к сожалению, не владею).

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

Для подавляющего большинства практиков

... формальные логические выводы в исчислении предикатов вообще не нужны.

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

Или в институте Клея тоже - противники аксиоматизации?

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

-- 15.07.2018, 15:43 --

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

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

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

-- 15.07.2018, 15:50 --

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

Затем вспомнил, что это как раз из-за спора о возможности выделить из слова $ (w_1, w_2) $ его «внутренние слова». И если вопрос о «внутренних словах» стоял для $P$-алгоритма, то он так же стоял и для $NP$-алгоритма. И полиномиальность относительно размера $|w_1|$ будет и полиномиальностью относительно размера $|(w_1, w_2)| $ и про слово $w_1$ тогда и говорить нечего, если не доказано, что это именно слово – что его можно считать словом.

Давайте я попробую угадать сразу на много шагов вперед: вы хотите показать, что существует язык $L$, распознающая его недетерменированная МТ $N$, представление каждого слова $w$ языка в виде $v_w \cdot u_w$, длина $w$ бывает неполиномиально больше длины $v_w$, такие что время работы $N$ на $w$ есть полином от $v_w$, а любая распознающая $L$ детерменированная МТ для любого полинома $p$ на некотором слова $w \in L$ работает дольше чем $p(|v_w|)$?

[Deggial]

Сообщение MerkulovaLE выделено в отдельную тему