Problem Detail: 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.
Asked By : Ran G.
Answered By : Aryabhata
Since you wanted “strings”, I mention the classic one: Post Correspondence Problem.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/178
