Y at-il un « naturel » la langue indécidable?

Question

Y at-il la langue « naturelle » qui est indécidable?

par « naturel » Je veux dire une langue définie directement par les propriétés des chaînes, et non par des machines et leur équivalent. En d'autres termes, si la langue ressemble $$ = L \ {\ langle M \ rangle \ mid \ ldots \} $$ où $ M $ est un TM, DFA (ou régulière exp), PDA (ou de grammaire), etc .., puis $ L $ n'est pas naturel. Toutefois $ L = \ {xy \ ldots \ mid x \ texte {est un préfixe y} \ ldots \} $ est naturel.

Answer 1

Puisque vous vouliez « cordes », je mentionne le classique. Poster Correspondance problème

Answer 2

Il y a de nombreux exemples mais voici quelques-unes:

• L'ensemble des vraies phrases dans la langue de arithmétique est indécidable.

• L'ensemble des phrases prouvable dans la théorie des ensembles (ZFC) est indécidable.

• L'ensemble des équations diophantiennes qui ont des solutions est indécidable.