Esiste un linguaggio indecidibile “naturale”?

Question

C'è un linguaggio "naturale", che è indecidibile?

di "naturale" intendo un linguaggio definito direttamente dalle proprietà di stringhe, e non tramite le macchine e il loro equivalente. In altre parole, se la lingua si presenta come $$ L = \ {\ langle M \ rangle \ metà \ ldots \} $$ dove $ M $ è una TM, DFA (o regolari-exp), PDA (o la grammatica), ecc .., quindi $ L $ non naturale. Tuttavia $ L = \ {xy \ ldots \ metà x \ text {è un prefisso di y} \ ldots \} $ è naturale.

Answer 1

Dal momento che si voleva "stringhe", cito quella classica:. corrispondenza postale problema

Answer 2

Ci sono molti esempi ma qui ci sono alcuni:

• L'insieme dei veri frasi nella lingua di aritmetica è indecidibile.

• L'insieme di frasi dimostrabili in teoria degli insiemi (ZFC) è indecidibile.

• L'insieme di equazioni diofantee che hanno soluzioni è indecidibile.