Las máquinas de Turing y las gramáticas sin restricciones son dos formalismos diferentes que definen los lenguajes RE. Algunos lenguajes RE son decidibles, pero no todos lo son.
Podemos definir los idiomas decidibles con las máquinas de Turing diciendo que un idioma es decidible si hay una TM para el idioma que detiene y acepta todas las cadenas en el idioma y detiene y rechaza todas las cadenas que no están en el idioma. Mi pregunta es esta: ¿existe una definición análoga de lenguajes decidibles basados en gramáticas sin restricciones en lugar de máquinas de Turing?
fuente
No puede haber una clase útil de gramáticas para (el conjunto de lenguajes recursivos), ya queR
El primero obviamente no es un teorema riguroso (y no puede serlo), es solo una conjetura de juicio. El conjunto de todas las gramáticas es enumerable, y cualquier restricción que no sea decidible probablemente no sea muy útil en sí misma; en particular no será una restricción sintáctica (como la de Chomsky).
El segundo es formalmente cierto, ver también aquí .
fuente
Esta pregunta se aborda en un documento de Henning Fernau de 1994. Henning afirma:
Dirigimos al lector que tiene curiosidad por aprender sobre esas extrañas propiedades del artículo.
fuente