Problem Detail: Are there undecidable properties of linear bounded automata (avoiding the empty set language trick)? What about for a deterministic finite automaton? (put aside intractability). I would like to get an example (if possible) of an undecidable problem that is defined without using Turing machines explicitly. Is Turing completeness of a model necessary to support uncomputable problems?
Asked By : Hernan_eche
Answered By : David Lewis
Undecidable problems about context free grammars, and hence, pushdown acceptors as well, which are restricted TMs from Wikipedia…
- Given a CFG, does it generate the language of all strings over the alphabet of terminal symbols used in its rules?
- Given two CFGs, do they generate the same language?
- Given two CFGs, can the first generate all strings that the second can generate?
There are many others about CFGs/PDAs as well as CSGs/LBAs and many other “simpler than TM” models.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/1697
