24
$\begingroup$

Is there any "natural" language which is undecidable?

by "natural" I mean a language defined directly by properties of strings, and not via machines and their equivalent. In other words, if the language looks like $$ L = \{ \langle M \rangle \mid \ldots \}$$ where $M$ is a TM, DFA (or regular-exp), PDA (or grammar), etc.., then $L$ is not natural. However $L = \{xy \ldots \mid x \text{ is a prefix of y} \ldots \}$ is natural.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
24
$\begingroup$

Since you wanted "strings", I mention the classic one: Post Correspondence Problem.

Improve this answer
$\endgroup$
0
21
$\begingroup$

There are many examples but here are a few:

  • The set of true sentences in the language of arithmetic is undecidable.

  • The set of provable sentences in set theory (ZFC) is undecidable.

  • The set of Diophantine equations which have solutions is undecidable.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.