Existe uma linguagem indecidível "natural"?

Existe alguma linguagem "natural" indecidível?

por "natural", quero dizer uma linguagem definida diretamente pelas propriedades das strings, e não através de máquinas e seus equivalentes. Em outras palavras, se o idioma se parecer com que é uma TM, DFA (ou exp regular), PDA (ou gramática) etc., então não é natural. No entanto, é natural.

$$L = \{ \langle M \rangle \mid \ldots \}$$ $M$$L$ $L = \{xy \ldots \mid x \text{ is a prefix of y} \ldots \}$

Como você queria "strings", mencionei o clássico: Problema de Pós-Correspondência .

Existem muitos exemplos, mas aqui estão alguns:

• O conjunto de sentenças verdadeiras na linguagem da aritmética é indecidível.

• O conjunto de frases prováveis ​​na teoria dos conjuntos (ZFC) é indecidível.

• O conjunto de equações diofantinas com soluções é indecidível.