Ghost_of_past про иерархию Хомского

[mihaild]

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

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

Но пока что получается, что для этой выразимости Вам, помимо исходной грамматики, нужна еще доказуемость. Которая обычно гораздо более сложная. Я не вижу, что в Ваших рассуждениях сломается, если мы придумаем какой-то вычислимый способ записывать формулы, в котором любая битовая строка будет формулой, и на основании этого объявим, что язык $\{0,1\}^*$ позволяет выразить что угодно.

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

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

Так товарищи утверждают, что не приписывают, а просто обнаруживают объективный факт. Я тоже не вижу особой ценности в приписывании температуре днем значения 35 градусов, но это ни на что не влияет.

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

А если мы заложим какой-то алгоритм прерывания повисшей аналитической грамматики, то скорее всего сделаем язык как минимум контекстно зависимым

Разрешимые языки, не являющиеся контекстно зависимыми, точно существуют. Элементарно язык из пар $(n, M)$, таких что $M$ - код МТ, останавливающейся на памяти $2^n$.

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

Модель в смысле теории моделей?

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

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

доказать эту формулу для тех значений аргумента

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

[Legioner93]

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

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

Интересно как! В цитате речь о теоремах "вообще", то есть "правильно" построенных словах? Про истинность/ложность/доказуемость теоремы речь не идёт?

То есть, $\forall x \in \mathbb{N} \to x+x > 1$ -- это теорема , но и $\forall x \in \mathbb{N} \to x+x > 2$ -- теорема, а вот $\forall x \in x+x > \mathbb{N} \to \forall$ -- уже не теорема, а абракадабра

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

А если всё же речь шла об истинных теоремах, то сомнительна даже перечислимость множества оных.

[mihaild]

Legioner93 в сообщении #1648102 писал(а):

В цитате речь о теоремах "вообще", то есть "правильно" построенных словах? Про истинность/ложность/доказуемость теоремы речь не идёт?

Теорема - это доказуемая формула.
Не-абракадабры - называются корректными (well formed) формулами.

[epros]

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

Я не вижу, что в Ваших рассуждениях сломается, если мы придумаем какой-то вычислимый способ записывать формулы, в котором любая битовая строка будет формулой, и на основании этого объявим, что язык $\{0,1\}^*$ позволяет выразить что угодно.

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

Если же Вы сказали это в смысле указания на бедность алфавита $\{0,1\}$ и имели в виду, что на этом алфавите должна быть определена любая грамматика, то я ничего не имею против этого, если грамматика будет разрешимой. На таком языке не удастся "выразить что угодно" разве что в том случае, когда количество предложений окажется конечным. Или наоборот, если грамматика окажется неразрешимой.

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

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

Так товарищи утверждают, что не приписывают, а просто обнаруживают объективный факт.

Это ещё нужно посмотреть, что именно и в каком контексте утверждают товарищи. Но объективного факта, что среди естественных языков встречаются неразрешимые, очевидно, быть не может.

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

Разрешимые языки, не являющиеся контекстно зависимыми, точно существуют. Элементарно язык из пар $(n, M)$, таких что $M$ - код МТ, останавливающейся на памяти $2^n$.

То, что существуют разрешимые языки, не являющиеся контекстно зависимыми, не вызывает сомнений. Я упомянул контекстно зависимые языки в том смысле, что это максимальный уровень в иерархии Хомского, к которому относятся гарантированно разрешимые языки.

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

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

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

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

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

Я понимаю, что числам нужно сопоставить замкнутые термы теории. И да, обычно это делается при построении модели в смысле теории моделей. Но мне не нужна полная интерпретация языка, обычно именуемая "моделью" заданной аксиоматики (ибо я всё равно считаю утверждение о существовании такой интерпретации неконструктивным надувательством). Мне достаточно доказательства того, что мы в состоянии записать формулу, которая в смысле предложенной нами аксиоматики и при условии интерпретации замкнутых термов (например, вида $0$, $S0$, $SS0$ и т.д.) как чисел, корректно моделирует произвольную частично рекурсивную функцию.

Legioner93 в сообщении #1648102 писал(а):

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

Речь о неполных (Гёдель называл их "достаточно содержательными") теориях. Остальные - мало интересны. mihaild абсолютно верно отметил, что множество теорем (т.е. доказанных утверждений теории) формально тоже является языком. По иерархии Хомского этот язык относится как раз к неограниченным. В этом смысле теория (т.е. её аксиоматика) является той грамматикой, которая определяет этот язык. Так что понятия "грамматики" и "аксиоматики" являются в некотором смысле взаимозаменяемыми.

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

В русском языке имеют значение правильные словоформы (падежные и прочие окончания слов). Так что для русского языка тоже есть пример, который придумал Л.В. Щерба: "Глокая куздра штеко бодланула бокра и кудрячит бокрёнка". Предполагается, что несмотря на бессмысленность слов, нормальный русский способен грамматически проинтерпретировать это как предложение: Какая-то (прилагательное женского рода в именительном падеже) самка (субъект женского рода в именительном падеже) как-то (наречие, признак действия) воздействовала в прошлом на (глагол совершенной формы женского рода) самца (обьект мужского рода в винительном падеже) и (союз, играющий роль логической связки) в настоящее время воздействует на (глагол несовершенной формы) детёныша (объект мужского рода в уменьшительной форме винительного падежа).

Забавно, что к этой "грамматической интерпретации" тут же был придуман контрпример: "Шашлычная турка сильно обманула казака и дурачит казачёнка".

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

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

[mihaild]

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

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

Да, именно так.

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

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

Я не понимаю, в каком смысле язык арифметики Пеано (множество корректных формул в соответствующей сигнатуре) позволяет выразить описание произвольной МТ, а язык $\{0, 1\}^*$ - нет. Я точно так же могу придумать вычислимые правила, по которым каждой МТ $M$ будет сопоставлена некоторая строка, паре (строка, сопоставленная какой-то МТ; $n$) будет сопоставлена еще некоторая строка ("результат подстановки") $s$, и эта строка будет выводиться по заданным мной правилам тогда и только тогда, когда эта МТ на пустом входе выдает число $n$. Это вроде бы полностью аналогично тому, что Вы говорили про "моделирование функций формулами арифметики".
Т.е. выражать что-то нам позволяет исчисление предикатов (грамматика типа 0), а не просто корректные формулы (которые традиционно берутся из грамматики типа 2, но т.к. они потом засовываются в гораздо более мощную грамматику, то в общем-то и такая выразительность избыточно, вполне можно было бы брать формулы из грамматики типа 4).

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

"абракадабры", как Вы выразились

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

[epros]

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

Я не понимаю, в каком смысле язык арифметики Пеано (множество корректных формул в соответствующей сигнатуре) позволяет выразить описание произвольной МТ, а язык $\{0, 1\}^*$ - нет. Я точно так же могу придумать вычислимые правила, по которым каждой МТ $M$ будет сопоставлена некоторая строка, паре (строка, сопоставленная какой-то МТ; $n$) будет сопоставлена еще некоторая строка ("результат подстановки") $s$, и эта строка будет выводиться по заданным мной правилам тогда и только тогда, когда эта МТ на пустом входе выдает число $n$. Это вроде бы полностью аналогично тому, что Вы говорили про "моделирование функций формулами арифметики".
Т.е. выражать что-то нам позволяет исчисление предикатов (грамматика типа 0), а не просто корректные формулы (которые традиционно берутся из грамматики типа 2, но т.к. они потом засовываются в гораздо более мощную грамматику, то в общем-то и такая выразительность избыточно, вполне можно было бы брать формулы из грамматики типа 4).

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

Википедия в статье про полноту по Тьюрингу писал(а):

it can be used to simulate any Turing machine

[mihaild]

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

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

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

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

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

Так что достаточно даже еще более простого. Настолько более простого, что это неинтересное свойство.

[Ghost_of_past]

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

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

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

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

тип 0 - неограниченные языки с логикой полиномиального времени
тип 1 - неограниченные минималистские языки
тип 2 - системные контекстно-свободные языки (грамматики с деревом из контекстно-свободных языков)
тип 3 - контекстно-свободные языки
тип 4 - индексируемые языки (контекстно-зависимые)
тип 5 - языки с логикой линейного времени (LTL)
тип 6 - полурегулярные языки
тип 7 - регулярные языки

В такой классификации естественные человеческие языки относятся к типам 1 и 2, но не к типу 0.

[mihaild]

Ghost_of_past в сообщении #1648338 писал(а):

языки с логикой линейного времени (LTL)

Там же по ссылке регулярный язык $(\neg | X)^* p (U(\neg |X)^*p)^*$ ($p$ - регулярное выражение для переменных). Или там в определении синтаксиса скобки забыли?

[Ghost_of_past]

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

Там же по ссылке регулярный язык

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

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

[mihaild]

Ghost_of_past в сообщении #1648340 писал(а):

Конкретно про связь языков с логикой линейного времени и регулярных языков можно посмотреть здесь

О, статья, написанная нормальным языком. Хотя и не везде - $O(|E|) = O(N)$ А в определении functional realizer забыли написать, что отображение собственно должно реализовывать заданный порядок.
Я правда не понимаю, какое отношение эта статья имеет к языкам с логикой линейного времени из википедии. Linear time там относится к сложности некоторого алгоритма на графах.

[epros]

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

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

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

Ghost_of_past в сообщении #1648338 писал(а):

тип 0 - неограниченные языки с логикой полиномиального времени

А что это такое? Это в точности то же, что вот здесь отнесено к типу 0? Или добавление слов про "логику полиномиального времени" означает что-то особенное?

[Ghost_of_past]

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

Я правда не понимаю, какое отношение эта статья имеет к языкам с логикой линейного времени из википедии.

Ну, связь между LTL и linear-time temporal logic вполне себе исторически сложившаяся. Насколько сейчас все это актуально и не пересматривалась ли: тут не могу сказать, так как это уже за пределами моих знаний.

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

Или добавление слов про "логику полиномиального времени" означает что-то особенное?

Отдельный подкласс рекурсивных языков. Идею его выделения в отдельный подкласс предложили еще в начале 1990ых годов (например, здесь).