¿Existe un lenguaje indecidible "natural"?

22

¿Hay algún lenguaje "natural" que sea indecidible?

por "natural" me refiero a un lenguaje definido directamente por las propiedades de las cadenas, y no a través de máquinas y su equivalente. En otras palabras, si las miradas del lenguaje como donde M es una MT, DFA (o regular-exp), PDA (o la gramática), etc .., entonces L no es natural. Sin embargo, L = { x y ... x  es un prefijo de y ... } es natural.

L={M}
ML L={xyx is a prefix of y}
Sonó.
fuente

Respuestas:

21

Hay muchos ejemplos, pero aquí hay algunos:

  • El conjunto de oraciones verdaderas en el lenguaje de la aritmética es indecidible.

  • El conjunto de oraciones comprobables en la teoría de conjuntos (ZFC) es indecidible.

  • El conjunto de ecuaciones diofantinas que tienen soluciones es indecidible.

Kaveh
fuente