Czy istnieje „naturalny” nierozstrzygalny język?

22

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 = {⟨ M ⟩ ∣ \dots}

$L = \{ \langle M \rangle \mid \ldots \}$

M

$M$

L

$L$

L = {x y \dots ∣ x is a prefix of y \dots}

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

— Ran G.
źródło

24

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

— Aryabhata
źródło

21

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.

— Kaveh
źródło