Надежные языки и неограниченная грамматика?

Машины Тьюринга и неограниченные грамматики - это два разных формализма, которые определяют языки RE. Некоторые языки RE разрешимы, но не все.

Мы можем определить разрешимые языки с помощью машин Тьюринга, сказав, что язык разрешимый, если есть язык для языка, который останавливает и принимает все строки в языке, а также останавливает и отклоняет все строки, не входящие в язык. Мой вопрос таков: есть ли аналогичное определение разрешимых языков, основанное на неограниченных грамматиках, а не на машинах Тьюринга?

computability turing-machines formal-grammars templatetypedef
источник

Ответы:

Язык разрешим, если он полуразрешим, а его дополнение полуразрешимо. Более того, язык является рекурсивно-перечислимым, если он полуразрешим, и поэтому вы можете найти неограниченную грамматику. Therfore:

Язык является разрешимой тогда и только тогда существует как неограниченный Грамматик с и неограниченный грамматик с . $L$ $G$ $L(G) = L$ $\bar G$ $L(\bar G) = \bar L$

Саймон С
источник

Кроме того, не являются ли «полуразрешимые» и «рекурсивно перечислимые» синонимы?

templatetypedef

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

Simon S

Вы ошиблись насчет определения разрешимости. «Решаемый» означает «есть машина Тьюринга, которая вычисляет ответ». Отношение, которое вы цитируете как определение, на самом деле является теоремой, которую я слышал, приписывая Эмилю Посту.

Андрей Бауэр

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

Андрей Бауэр

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

Simon S

Не может быть полезного класса грамматик для (множество рекурсивных языков), так как $\mathrm{R}$

каждый полезный класс грамматик перечисляем, и
$\mathrm{R}$ не является полуразрешимым или, что эквивалентно, не перечисляемым.

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

Второе формально верно, см. Также здесь .

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

Рафаэль
источник

Почему этот аргумент также не применим к машинам Тьюринга? Существует полезный класс TM для R (решающие факторы), даже если они не перечислимы.

templatetypedef

@templatetypedef: эта мысль пришла мне в голову. 1) Набор машин Тьюринга для R несколько «нематериален». Возможно, это не «полезно» ни в каком, кроме самого теоретического смысла. 2) ТМ является оперативной моделью, тогда как грамматики являются скорее декларативной (если порождающей) моделью. Следовательно, маловероятно, что существует даже такое свойство, как «бесполезное», как у R-TM. (Опять же, все это болтовня, основанная на интуиции.)

Рафаэль

Этот вопрос рассматривается в статье Хеннинга Фернэу от 1994 года. Хеннинг заявляет:

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

Мы направляем читателя, который хочет узнать об этих странных свойствах, к статье.

Юваль Фильмус
источник