patternMajor
Is there a "natural" undecidable language?
Viewed 0 times
thereundecidablenaturallanguage
Problem
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.
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.
Solution
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.
-
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.
Context
StackExchange Computer Science Q#178, answer score: 21
Revisions (0)
No revisions yet.