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

[dmitgu]

epros в сообщении #1313612 писал(а):

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

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

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

Что значит "слово $Y$ является словом для языка"?

Давайте вспомним про определения (скопировал из Вики).

Формальный язык в математической логике и информатике — множество конечных слов (строк, цепочек) над конечным алфавитом.
Слово формального языка (также — цепочка, строка) — произвольная последовательность символов из данного алфавита.

Так вот - про подстроки в слове ничего не сказано. В то же время их можно считать словами - это практика. То есть - тут нет противоречий. Поэтому делаем вот что:

1. Логическое расширение для понятия «слово» – следующая аксиома:
Подстрока $\text{«блаблабла»}$ внутри слова – тоже слово
2. Язык $G$ – это такое множество слов:
Слова, не содержащие внутри себя ни одного слова $\text{«блаблабла»}$.

Теперь всё понятно? ) И про "алгоритм, распознающий язык" теперь, оказывается - важно учитывать и аксиомы про слова. Заметим, что в данном примере в качестве слова признаётся лишь подстрока $\text{«блаблабла»}$, про остальные подстроки ничего не сказано, и расширить теорию языка можно аксиомами про другие подстроки и в сторону "слово" и в сторону "не слово" - но нам это не требуется.

А определение языка строится так, что выделять надо именно слово $\text{«блаблабла»}$ - только от него и зависит множество И отсюда следует свойство алгоритма, распознающего язык:

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

Алгоритм $A_G$ распознаёт язык $G$, если считывающая головка после чтения слова $Y$ прекращает дальнейшее чтение «входных данных» на ленте и выдаёт $0$ (ноль) – «слово не принадлежит языку $G$».

[mihaild]

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

Так вот - про подстроки в слове ничего не сказано. В то же время их можно считать словами - это практика

А зачем дополнительно говорить? Подстрока - это по определению слово.

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

1. Логическое расширение для понятия «слово» – следующая аксиома:
Подстрока $\text{«блаблабла»}$ внутри слова – тоже слово

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

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

2. Язык $G$ – это такое множество слов:
Слова, не содержащие внутри себя ни одного слова $\text{«блаблабла»}$.

Нет, непонятно.

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

Давайте еще запретим слово "внутри".

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

в данном примере в качестве слова признаётся лишь подстрока $\text{«блаблабла»}$

В примере чего? Языка? Что значит "$x$ признается в качестве слова"?

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

расширить теорию языка

Что такое "теория языка"?

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

А определение языка строится так, что выделять надо именно слово $\text{«блаблабла»}$

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

[dmitgu]

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

Что такое "подстрока внутри слова"?

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

К счастью, Вы сами даёте материал из формализма для ответа на предыдущий вопрос:

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

Если это, скажем, кортеж "(слово, индекс начала подстроки, индекс конца подстроки)" - то такая конструкция словом уже не является, т.к. слово, по определению - последовательность символов, а этот кортеж последовательностью символов не является.

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

Вы можете доказать, что кортеж не является словом? Может, я не правильно понимаю термин «кортеж», но то, что в слове находится от индекса начала до индекса конца и равно $\text{«блаблабла»}$ у меня аксиоматизируется как слово. Не только кортеж, но ещё и слово ) А понятие «внутри» или «в» для этого $\text{«блаблабла»}$ означает то же, что и в выражении «кортеж в слове». Я же аксиоматизировал это.

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

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

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

А корректно ли таким образом доказывать $NP \ne P$? Аксиоматизировав особые свойства слов? Да, на мой взгляд. Например: если у нас есть 4 аксиомы геометрии (без аксиомы параллельных) и стоит вопрос – можно ли доказать на их базе аксиому Евклида – то можно сделать вот что (и это было сделано): Построить модель интерпретации (особую поверхность) с особыми свойствами, которые будут добавлены по сравнению с 4-мя исходными аксиомами (особые свойства для особой поверхности) и доказать, что аксиома Евклида может и не исполняться при исполнении 4-х базовых аксиом.

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

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

вы пока что никакого своего определения языка не предложили

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

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

[mihaild]

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

Вы можете доказать, что кортеж не является словом?

Ну, по определению, слово - это функция $\{0, \ldots, n\} \to A$ для некоторого $n$. Т.е. множество пар вида $(i, a)$. Кортеж $\langle x, y, z\rangle$ формально - это $\{x, \{x, \{y, \{y, \{z, \{z, \varnothing\}\}\}\}\}\}$. Доказательство того, что эта штука не является множеством пар вида $(\text{число}, \text{символ})$, если $x$ является множеством пар такого вида (т.е. словом), оставляю вам в качестве упражнения.

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

На самом же деле, то, что не оговорено в теории допускает «что угодно»,

Определения обычно имеют вид "$x$ - это $y$, такой что $z$". И если дано такое определение, то то, что не является $y$, не является и $x$. И то, для чего не выполнено $z$, тоже не является $x$.
Т.е. если дано определение "слово - это функция откуда-то куда-то", то оно в частности означает, что то, что не является функцией, не является и словом.

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

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

Ну смотрите, в терминах C++17 - есть std::string и есть std::string_view. Если у вас есть std::string s = "abcdef";, то из std::string_view(&s[2], 3); можно извлечь больше информации, чем из s.substr(2, 3) - по первой можно понять, из какого слова ее брали, по второй - нельзя. Это разные объекты.
Понятно, как сделать string из string_view, но при этом теряется информация. Точно также понятно, как из кортежа "(строка, индекс начала, индекс конца)" сделать строку, но при этом теряется информация - разным таким кортежам будет соответствовать одна и та же строка.

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

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

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

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

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

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

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

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

Определения не будет, потому что нужна аксиома - нечто, допускающее альтернативу (другую аксиому).

Ну если нет определения, то нет и формулировки задачи, и непонятно о чем был разговор на два с лишним десятка страниц:)

Я пока что вижу два варианта: вы либо формулируете всё, что хотите сказать, начиная с базовых понятий теории множеств (понятие "функция" считаем известным, понятие "слово" уже не считаем). Либо вы берете стандартные формулировки, и на их основании вводите новые - например, "слово по dmitgu - это элемент множества $\text{все слова} \cup \text{кортежи такого-то вида} \cup \{\text{желтые ботинки}\}$".

Укажите, пожалуйста, явно, какой из этих вариантов вы предпочитаете, или предложите свой.

[dmitgu]

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

dmitgu в сообщении #1314544
dmitgu:
Вы можете доказать, что кортеж не является словом?
mihaild:
Ну, по определению, слово - это функция $\{0, \ldots, n\} \to A$ для некоторого $n$. Т.е. множество пар вида $(i, a)$. Кортеж $\langle x, y, z\rangle$ формально - это $\{x, \{x, \{y, \{y, \{z, \{z, \varnothing\}\}\}\}\}\}$. Доказательство того, что эта штука не является множеством пар вида $(\text{число}, \text{символ})$, если $x$ является множеством пар такого вида (т.е. словом), оставляю вам в качестве упражнения.

Объясните мне, пожалуйста, чем Ваши обозначения отличаются от нумерации?
Ну, входит в "нумерацию" кортежа ещё и слово - и что? Вы может доказать, что для кортежа символов в данном слове от символа № $(x, k_1)$ до символа № $(x, k_2)$, $(k_1 \le k_2)$ включительно нет нумерации от $1$ до $(k_2 - k_1 + 1)$, при этом номер $(k_2 - k_1 + 1)$ в этой нумерации – последний? Очень сильно сомневаюсь в возможности такого доказательство :) Странно (из нашей практики), что нет обратного доказательства – о наличии соответствующей нумерации. А если есть такая нумерация, то есть и слово, соответствующее данному кортежу внутри слова. Вот и получаем слово («внутреннее слово») внутри другого слова («слова-контейнера»).

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

Ну смотрите, в терминах C++17 - есть std::string и есть std::string_view. Если у вас есть std::string s = "abcdef";, то из std::string_view(&s[2], 3); можно извлечь больше информации, чем из s.substr(2, 3) - по первой можно понять, из какого слова ее брали, по второй - нельзя. Это разные объекты.
Понятно, как сделать string из string_view, но при этом теряется информация. Точно также понятно, как из кортежа "(строка, индекс начала, индекс конца)" сделать строку, но при этом теряется информация - разным таким кортежам будет соответствовать одна и та же строка.

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

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

Ну если нет определения, то нет и формулировки задачи, и непонятно о чем был разговор на два с лишним десятка страниц:)

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

Хитрые обозначения ведь не создают новые объекты - Вот, например, определим понятием «выражение 1» такое выражение: $1+1$, а понятием «выражение 2» такое выражение: $4/2$. Они обозначают одно и то же – двойку, хотя понятия сами по себе разные – и по названию и разные выражения там.

[mihaild]

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

Объясните мне, пожалуйста, чем Ваши обозначения отличаются от нумерации?

Не понимаю вопроса. Какие именно обозначения от нумерации чего?

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

Вы может доказать, что для кортежа символов в данном слове от символа № $(x, k_1)$ до символа № $(x, k_2)$, $(k_1 \le k_2)$ включительно нет нумерации от $1$ до $(k_2 - k_1 + 1)$, при этом номер $(k_2 - k_1 + 1)$ в этой нумерации – последний?

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

Я вообще не очень понимаю, о чем спор. "Слово в алфавите $A$" - это просто другое название "функции в из $\{0, \ldots, n\}$ в $A$". Всё, что не является такой функцией, не является словом. Просто по определению.
Можно вводить другие понятия, но их надо как-то обозначать. А не добавлять в уже имеющиеся термины новые смыслы, сильно отличающиеся от изначальных.

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

А если есть такая нумерация, то есть и слово, соответствующее данному кортежу внутри слова.

Слово, "соответствующее" данному кортежу $\langle \text{слово}, \text{индекс начала}, \text{индекс конца}\rangle$, безусловно есть. Формально, кортежу $\langle f, n, m\rangle$ соответствует слово $g$, имеющее длину $m - n + 1$, такое что $g(i) = f(i + n)$.
Термин "внутри" тут либо лишний, либо несущий какой-то непонятный мне смысл.

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

Да, вот только Вашему формализму эта практика не соответствует.

Ну да, слово с собой никакой "идентификатор" не таскает. А еще в теории множеств нет явного аналога конструкции s[2] = 'x';.
Оказывается, что удобнее сначала определить иммутабельные объекты, а потом уже на их основе вводить изменяемые - как функцию из моментов времени в неизменяемые.
Можно вводить другие конструкции, но это, во-первых, непонятно зачем нужно, а во-вторых, это должен делать тот, кому они нужны.

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

А у Вас символы как "электроны" - они тождественны во всех словах

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

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

Но тогда и кортеж из таких символов - и нечего указывать исходное слово в определении кортежа

Еще раз. Можно ввести два разных понятия "подслова". Можно - просто как слово с нужными условиями. Тогда, хотя и можно определить, является ли одно слово подсловом другого, если у нас есть слово $aba$, нельзя сказать, получено ли слово $a$ как подслово из первой или из третьей буквы.
Можно - как "вхождение подслова". Тогда это будет именно кортеж $\langle \text{слово}, \text{индекс начала}, \text{индекс конца}\rangle$ - эта конструкция помнит, из какого слова она извлечена, и по ней можно построить строку, являющуюся подсловом (см. выше). Но при этом мы получим, скажем, $ - придется вводить другое отношение эквивалентности.
Кроме того, начинать нам придется всё равно с "обычных" слов - последовательностей символов. Ну и требовать, что каждое встречающееся слово откуда-то "извлечено", крайне неудобно.

Можно рассмотреть "расширенное множество слов", состоящее из слов, а также кортежей указанного вида, и ввести на нем отношение эквивалентности "задают одно и то же слово". Можно сделать что-то еще. Но это надо сделать явно.

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

мне то кажется, что я говорю очевидные вещи

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

(Оффтоп)

Я вел семинары по программированию, и если бы я пытался объяснять алгоритмы на вашем уровне строгости, меня бы уволили, и правильно бы сделали.

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

Хитрые обозначения ведь не создают новые объекты

В терминах теории множеств объекты вообще "не создаются" - они уже "есть" (в модели) [ну или их уже нет и не будет].

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

Они обозначают одно и то же

Ну как же одно и то же? В выражении 1 есть символ $+$, а в выражении 2 такого символа нет. Это разные слова.
Нам нужны какие-то дополнительные правила, чтобы можно было сказать "эти выражения задают один и тот же объект". И если копать дальше - то мы и придем к исчислению предикатов (или чему-то подобному).

[dmitgu]

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

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

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

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

С чего Вы взяли, что слово - это множество пар $\{i, smb\}$, где $i$ пробегает все значения целых чисел от $1$ до некоторого $N$? Ведь для слова важен лишь порядок расположения символов – поэтому $i$ может быть из любого набора не повторяющихся положительных натуральных чисел – и не только чисел, кстати – необходимо лишь наличие порядка и уникальность в нумераторе. А зададим мы слово $\text{«блаблабла»}$ множеством пар:

$\{1, \text{«б»} \}$, $\{2, \text{«л»}\}$, $\{3, \text{«a»}\}$, $\{4, \text{«б»}\}$, $\{5, \text{«л»}\}$, $\{6, \text{«a»}\}$, $\{7, \text{«б»}\}$, $\{8, \text{«л»}\}$, $\{9, \text{«a»}\}$

Или таким образом:

$\{10, \text{«б»}\}$, $\{90, \text{«л»}\}$, $\{91, \text{«a»}\}$, $\{213, \text{«б»}\}$, $\{367, \text{«л»}\}$, $\{999, \text{«a»}\}$, $\{8880, \text{«б»}\}$, $\{8881, \text{«л»}\}$, $\{9999, \text{«a»}\}$

Никакой разницы!

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

$\{91, \text{«a»}\}$, $\{213, \text{«б»}\}$, $\{367, \text{«л»}\}$, $\{999, \text{«a»}\}$, $\{8880, \text{«б»}\}$, $\{8881, \text{«л»} \}$

А может и другой:

$\{1, \text{«a»}\}$, $\{2, \text{«б»}\}$, $\{3, \text{«л»}\}$, $\{4, \text{«a»}\}$, $\{5, \text{«б»}\}$, $\{6, \text{«л»} \}$

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

Поэтому очевидно – при таком подходе – что в слове любые выбранные в нём подстроки (и даже любые подмножества) – тоже слова.

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

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

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

[mihaild]

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

Никакой разницы!

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

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

термин «слово» в книгах и Интернете определяют как «цепочку», «строку», но не как множество пар с фиксированной нумерацией

"Слово" и "строка" в этой области - это синонимы, ну и явно это не определение.

Верещагин, Шень. Языки и исчисления, стр. 189 писал(а):

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

.
Определения конечной последовательности мне внезапно найти в нормальных источниках не удалось (mathworld дает определение "упорядоченное множество математических объектов", что явно не является определением вообще - что такое "математический объект"? ну и считать множество вещественных чисел последовательностью ИМХО странно). Есть, скажем

Rudin, Principles of Mathematical Analysis, стр. 26 писал(а):

By a sequence, we mean a function f defined on the set J of all positive integers.

Но вообще - не так важно, о каких определениях конкретно договариваться, важно договориться о каких-то и дальше это не менять.
Можно называть типа-словом функцию из какого-то конечного подмножества натуральных чисел в алфавит. Такое определение вас устроит?
При этом нужно договориться, какие типа-слова считать равными. Скажем, $f: \{0\} \to A, f(0) = x$ и $f: \{42\} \to A, f(42) = x$ - это одно типа-слово или разные?
Если одно, то для каждого типа-слова существует единственное равное ему типа-слово, являющееся словом - и, если не следить за конкретной нумерацией, а только за порядком, не очень понятно, зачем вообще нужны типа-слова, не являющиеся словами - просто выберем из каждого класса эквивалентности по одному такому представителю; это создаст некоторые мелкие технические сложности при выделении подпоследовательностей, зато избавит от сложностей в других местах.
Но непринципиально, если такое определение вас устраивает - давайте его зафиксируем и поедем дальше, к "словам внутри слов" и прочим непонятным "внутренним" штукам.

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

Кстати, функция – это не множество пар (как Вы это написали), а отношение между множествами.

А что по-вашему такое "отношение между множествами", если не множество пар? См. "Основы теории множеств", стр. 32, например.
(да, я тут выше слегка напутал, и вас, возможно, с толку сбил - пары там конечно упорядоченные надо брать)

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

И кортеж (информатика) в Вики описывается совсем не так, как у Вас

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

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

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

Определения не бывают ошибочными.

[mihaild]

Заметим, что и на практике (в программах, в учебниках и статьях по программированию и алгоритмам) точно также не встречаются выражения вида "слово внутри слова" и "внутреннее содержание слова". Если хотите, можно считать слово "интерфейсом" с двумя функциями - получения длины и получения $i$-го символа.
(это как раз очень хорошо описывается определением "слово - функция из начального отрезка натурального ряда в алфавит")
А дальше через этот интерфейс можно уже выражать что угодно - например, "слово $x$ является подсловом слова $y$", "подслово слова $x$, начинающееся с $i$-й позиции и имеющее длину $k$" и т.д.

[dmitgu]

Об отсутствии теории

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

Определения конечной последовательности мне внезапно найти в нормальных источниках не удалось (mathworld дает определение "упорядоченное множество математических объектов", что явно не является определением вообще - что такое "математический объект"? ну и считать множество вещественных чисел последовательностью ИМХО странно)

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

Конечно, формализм мы можем сделать и сами (если Вы не против) – хотя бы какие-то нужные уже сейчас основы теории языков. Какой уже раз тут такие «сюрпризы» с формализмом. Это продуктивно, конечно, но иногда думаешь: «Я слишком стар для этого …» (с) Дэнни Гловер :)))

Про «разница есть».

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

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

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

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

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

Определение не может быть ошибочным?

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

Определения не бывают ошибочными.

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

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

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

Например, если бы слова были определены как:

1. Конечные множества пар (номер, символ) и

2. Нумерацию можно использовать произвольную,

3. Но при этом строки не равны, даже при одинаковых символах, одинаковом их количестве и порядке в словах, но, если конкретные номера на одинаковых местах при данном порядке не равны в сравниваемых словах.

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

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

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

Но вообще - не так важно, о каких определениях конкретно договариваться, важно договориться о каких-то и дальше это не менять.
Можно называть типа-словом функцию из какого-то конечного подмножества натуральных чисел в алфавит. Такое определение вас устроит?
При этом нужно договориться, какие типа-слова считать равными. Скажем, $f: \{0\} \to A, f(0) = x$ и $f: \{42\} \to A, f(42) = x$ - это одно типа-слово или разные?

Если говорить о порядке на основе нумератора без повторов в духе $(i, smb)$… Наличие такого нумератора, который обладает внешним (по отношению к самой строке) порядком, кажется добавлением излишних свойств к тому, чем должна обладать строка в «базовом» случае. Вообще сомнительно, что несколько подстрок могут «склеиваться» в одно слово, если выделить их внутри слова в некое подмножество. Не факт, что в исходном слове должен быть порядок между фрагментами, если эти фрагменты разделены «дырами».

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

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

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

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

Набросок для теории языков

Для построения слова берём стек, каждый элемент которого имеет такой вид:

$(id_{this}, smb, id_{next})$, где $smb$ – некоторый символ, а $id_{this}$ и $id_{next}$ берутся из какого-то ограниченного набора $id$ со следующими свойствами:

1. Каждый $id$ используется не больше 1 раза как $id$ элемента ($id_{this}$ - все элементы однозначны)

2. Каждый $id$ используется не больше 1 раза как $id$ следующего ($id_{next}$ - отношения следования элементов однозначны)

3. Только один $id$ не используется как $id$ элемента ($id_{this}$)

4. Только один $id$ не используется как $id$ следующего ($id_{next}$)

5. Это разные $id$ (в двух предыдущих пунктах)

6. Все способы выбора набора $id$ и расстановки $id$ в элементах дают одно и то же слово из данных символов – если исполнены предыдущие пункты и сохраняется прежний порядок, с началом из п.7 и выполнены условия п.8

7. Началом порядка считаем элемент с $id_{next}$ из п.3, а концом – элемент с $id_{this}$ из п.4

Начало и конец порядка симметричны при данных правилах с точностью до обмена названиями «полей» (термин из информатики для составных частей элемента) в элементах между $id_{this}$ и $id_{next}$. Действительно, тогда $id$ из п.3 становится $id$ из п.4 и наоборот, а п.6 остаётся в силе (обмены – в названиях полей, но не в правилах).

В данном стеке (а описанные в пп. 1-7 элементы является элементами стека – если использовать термин из программирования) поле $id_{next}$ названо не совсем обычно. В программе оно называлось бы в духе $id_{previous}$ ($id$ предыдущего), скорее всего:

Потому что у стека есть одна «вершина» куда помещается новый элемент, и он сам становится новой вершиной с $id_{previous}$ равным $id_{this}$ предыдущего элемента (если предыдущий элемент был), затем так же добавляется следующий элемент и т.д. Затем «вершину» можно забрать (убрать) и актуальной вершиной станет предыдущий для него элемент (номер $id_{this}$ которого получена из поля $id_{previous}$ убранной вершины) и т.д. Работает такая структура в программах по принципу «последним вошёл – первым вышел».

Но в слове «вершина» стека у нас становится началом слова, так как, зная этот 1-й элемент, можно последовательно пробежать все последующие элементы $(id_{this}, smb, id_{next})$ «прыгая» к $id_{this}$ следующего элемента, равного $id_{next}$ текущего.

8. Сразу надо оговорить те два набора значений для $id$, которые можно использовать на краях слова – для $id_{this}$ первого элемента и $id_{next}$ последнего элемента в слове. Эти наборы и будут ограничивать возможности переписать $id$ в элементах при сохранении порядка.

Например, для п.3 (задающего начало слова) годится только $1$ в качестве его $id_{this}$ и больше он нигде (кроме начала) не используется, А для п.4 (для конца слова) годится только $2$ в качестве его $id_{next}$ с аналогичными условиями. Тогда у слова «запечатаны» оба конца, и оно «неделимо» – его сплошные фрагменты (меньшие, чем целое слово) не являются словами.

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

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

Если говорить о словах на примере строк в компьютерных программах, то для начала и конца слова разрешены любые $id$ – концы у слов не «запечатаны». Поэтому можно брать любую подстроку (прямо внутри исходного слова) и это тоже будет слово – операция логического равенства между такой подстрокой и некоторым словом (строкой) даст «истина». Это «некоторое слово» имеет тот же порядок и символы, что и подстрока, конечно.

«Компьютерный» способ выделения слов можно считать принципиальным для теории алгоритмов – ведь работа компьютеров нацелена на исполнение алгоритмов. То есть, тут для теории алгоритмов прикладная область и проверка на практике.

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

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

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

Видимо, неравенство $NP \ne P$ можно доказать и для «неделимых» слов, но это уже отдельный вопрос и такое доказательство более трудное, по всей видимости.

Сведения из программирования

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

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

В программировании вообще термин «слово» не особо используется. К тому же «строка» в C (C#. C++) имеет на конце символ ‘0’. К тому же тип String вообще неизменный, а тип StringBilder возвращает подстроки типа String – то есть, не свой внутренний фрагмент. Но это же просто особенность реализации – как и конкретная нумерация символов, например. Если же говорить про последовательность символов, которая допускает получать внутренние фрагменты, то удобней рассмотреть объект Range языка VBA для Word – в тексте задаётся начальная и конечная позиция.

А последовательность символов (семейство символов – «Characters collection» – в реализации VBA), которая этому объекту соответствует, можно получить через свойство Range.Characters. И вот можно брать внутри одного объекта Range (пусть $rng_1$) другой (вложенный) объект Range (пусть $rng_2$). И соответствующие им «слова» будут последовательностями символов, при этом у $rng_2$ «слово» будет соответствовать фрагменту из исходного «слова» $rng_1$. То есть, когда мы «очищаем» данные от реализации (специфического представления в данном языке), то фрагменты одних слов тоже оказываются словами – то есть объектами того же типа.

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

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

[dmitgu]

Пардон, в "наброске для теории языков" у меня опечатка (заметил поздно для редактирования) в п. 7. Вместо

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

7. Началом порядка считаем элемент с $id_{next}$ из п.3, а концом – элемент с $id_{this}$ из п.4

Надо:

7. Началом порядка считаем элемент с $id_{this}$ из п.4, а концом – элемент с $id_{next}$ из п.3

-- 03.06.2018, 12:30 --

Ну, и соответственно, в п. 8 вместо:

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

Например, для п.3 (задающего начало слова) годится только $1$ в качестве его $id_{this}$ и больше он нигде (кроме начала) не используется, А для п.4 (для конца слова) годится только $2$ в качестве его $id_{next}$ с аналогичными условиями. Тогда у слова «запечатаны» оба конца, и оно «неделимо» – его сплошные фрагменты (меньшие, чем целое слово) не являются словами.

Надо:
Например, для п.4 (задающего начало слова) годится только $1$ в качестве его $id_{this}$ и больше он нигде (кроме начала) не используется, А для п.3 (для конца слова) годится только $2$ в качестве его $id_{next}$ с аналогичными условиями. Тогда у слова «запечатаны» оба конца, и оно «неделимо» – его сплошные фрагменты (меньшие, чем целое слово) не являются словами.

[mihaild]

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

Получается, у нас и готовой теории для языков нет?

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

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

между правильной теорией и реальностью есть связь

Не знаю, что такое "реальность". И буква "М" в названии раздела означает, что в этом разделе и не надо про это знать.

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

И связь эта опирается на «стандартную модель интерпретации». Для теории Пеано, например, эта модель – операции с реальными «счётными палочками», например.

Это неправда. Стандартная модель PA - это множество с заданными на нем операциями.
(кстати, "модель интерпретации" не говорят, говорят "модель теории")

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

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

Такого быть не может - иначе бы мы смогли из этого сделать полное эффективное непротиворечивое расширение PA.

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

Если говорить о порядке на основе нумератора без повторов в духе $(i, smb)$… Наличие такого нумератора, который обладает внешним (по отношению к самой строке) порядком, кажется добавлением излишних свойств к тому, чем должна обладать строка в «базовом» случае.

Ну ок, давайте рассмотрим все функции вида $\text{конечное подмножество \mathbb{N}} \to A$, введем на нем отношение эквивалентности: $f \sim g \leftrightarrow \exists q: \mathbb{N}\to\mathbb{N}, q \nearrow: f = g \circ q$. И будем называть словом класс эквивалентности относительно этого отношения.
Теперь отождествим каждый класс с его представителем, имеющим областью определения $\{0, \ldots, n - 1\}$, и получим стандартное определение.

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

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

Для построения слова берём стек

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

Вам от "интерфейса" строк нужно что-то, кроме понятия "$i$-й символ"? Стандартные штуки можно легко выразить через него: например, строка $s_1$ является подстрокой строки $s$, если $\exists n: \forall i < |s_1|: s[n + i] = s_1[i]$.
Или вы хотите придумать формализм, в котором (подстрока строки $ab$ длины $1$, начинающаяся с 1го символа) отличается от (подстрока строки $bb$ длины $1$, начинающаяся с 1го символа)?

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

[Someone]

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

давайте спросим у Someone

Что именно? Я слабо слежу за вашей дискуссией, поскольку ни в малейшей степени не специалист в обсуждаемой области, поэтому боюсь не угадать. Прошу уточнить вопрос.

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

Стандартная модель PA - это множество с заданными на нем операциями.

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

А что такое "стандартная модель интерпретации" — не знаю. Сочетание слов "модель интерпретации" выглядит бессмысленным. Ибо есть понятие интерпретации формальной теории, и есть понятие модели как интерпретации, удовлетворяющей определённым условиям.

[mihaild]

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

Что именно?

Утверждение, что существует такая последовательность графов $G_n$ и полиномиальная недетерменированная машина Тьюринга $N$, проверяющая ну скажем 3-раскрашиваемость графов, такие что для любой детерменированной МТ $M$, проверяющей графы на 3-раскрашиваемость, верно $T_N(G_n) = o(T_M(G_n))$.
(я не говорю, что это доказано или хотя бы утверждается, но кажется что если предлагаемое рассуждение вообще возможно превратить во что-то строгое, то получится примерно это)

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

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

Да, имелось в виду "модель - это множество (а не реальный физический объект)".

[Someone]

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

Утверждение, что существует такая последовательность графов $G_n$ и полиномиальная недетерменированная машина Тьюринга $N$, проверяющая ну скажем 3-раскрашиваемость графов, такие что для любой детерменированной МТ $M$, проверяющей графы на 3-раскрашиваемость, верно $T_N(G_n) = o(T_M(G_n))$.
(я не говорю, что это доказано или хотя бы утверждается, но кажется что если предлагаемое рассуждение вообще возможно превратить во что-то строгое, то получится примерно это)

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