Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

up vote 16 down vote accepted

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

share|improve this answer
    
Or did I miss something? –  Aryabhata Mar 10 '12 at 5:32
    
How come I didn't think about it?! –  Ran G. Mar 10 '12 at 5:51
    
Excellent example. –  Janoma Mar 10 '12 at 6:00
    
Although Kaveh's answer is more complete, I'll accept this question because it is simple, elegant, and classic! –  Ran G. Mar 10 '12 at 18:28
    
To generalize this answer, also the Tiling problem (aka: domino problem) is undecidable. It can be seen as a natural 2D variant of (the single-dimension) PCP. –  Ran G. Feb 26 '13 at 5:53

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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