patternModerate
Are there undecidable properties of non-turing-complete automata?
Viewed 0 times
undecidablenonarepropertiesautomatacompleteturingthere
Problem
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?
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?
Solution
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.
-
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.
Context
StackExchange Computer Science Q#1697, answer score: 15
Revisions (0)
No revisions yet.