Gibt es eine "natürliche" unentscheidbare Sprache?

22

Gibt es eine "natürliche" Sprache, die unentscheidbar ist?

mit "natürlich" meine ich eine sprache, die direkt durch die eigenschaften von strings definiert ist und nicht über maschinen und deren äquivalent. Mit anderen Worten, wenn die Sprache wie folgt aussieht: wobei TM, DFA (oder reguläre Exp), PDA (oder Grammatik) usw. ist, dann ist nicht natürlich. Jedoch ist natürlich.

L={M}
ML L={xyx is a prefix of y}
Ran G.
quelle

Antworten:

21

Es gibt viele Beispiele, aber hier sind einige:

  • Die Menge der wahren Sätze in der Sprache der Arithmetik ist nicht zu entscheiden.

  • Die Menge der beweisbaren Sätze in der Mengenlehre (ZFC) ist unentscheidbar.

  • Die Menge der Diophantine-Gleichungen, die Lösungen haben, ist nicht zu entscheiden.

Kaveh
quelle