Czy istnieje „naturalny” nierozstrzygalny język?

Czy istnieje jakiś „naturalny” język, który jest nierozstrzygalny?

przez „naturalny” rozumiem język zdefiniowany bezpośrednio przez właściwości ciągów, a nie przez maszyny i ich odpowiedniki. Innymi słowy, jeśli język wygląda jak gdzie to TM, DFA (lub regularny exp), PDA (lub gramatyka) itp., To nie jest naturalne. Jednak jest naturalne.

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

Ponieważ chciałeś „ciągów”, wspomniałem o klasycznym: problem z korespondencją .

Istnieje wiele przykładów, ale oto kilka:

• Zbiór prawdziwych zdań w języku arytmetyki jest nierozstrzygalny.

• Zbiór zdań możliwych do udowodnienia w teorii mnogości (ZFC) jest nierozstrzygalny.

• Zbiór równań diofantycznych z rozwiązaniami jest nierozstrzygalny.