¿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.