Есть ли «естественный» неразрешимый язык?

22

Есть ли какой-нибудь "естественный" язык, который неразрешим?

под «естественным» я подразумеваю язык, определяемый непосредственно свойствами строк, а не с помощью машин и их эквивалентов. Другими словами, если язык выглядит как где - это ТМ, DFA (или регулярное выражение), КПК (или грамматика) и т. Д., То это не естественно. Однако , естественно.M L L = { х у ... | х  является префиксом у ... }

L={⟨M⟩∣…}
ML L={xy…∣x is a prefix of y…}
formal-languages automata computability undecidability Ран Г.
источник

Ответы:

21

Есть много примеров, но вот несколько:

  • Множество истинных предложений на языке арифметики неразрешимо.

  • Множество доказуемых предложений в теории множеств (ZFC) неразрешимо.

  • Система диофантовых уравнений, которые имеют решения, неразрешима.

Кава
источник