The following are also decidable by simulation and equivalence of DFA, NFA, and regular expressions.
is decidable performing a tree search for accept state from start state.
is decidable by constructing such that , and testing if .
is decidable by converting to Chomsky normal form, and finding all derivations of length . Any derivation of this length will take at most steps.
is decidable by marking all terminal symbols, and then marking all variables that have marked children. If the start symbol is marked, then there is some string in . There are only variables, so this algorithm will terminate.
Undecidable Languages
The set of Turing-recognizable languages are countable, but the set of all languages is uncountable since is not
is undecidable, but recognizable. The second property can be seen by simply running on . The first property requires additional construction. Assume is decidable with decider and construct .
Running , we get a contradiction, since both and fail to satisfy the condition on . Thus cannot exist and is undecidable.
A language is co-Turing recognizable if it is the complement of a Turing recognizable language. A language is decidable iff it is Turing recognizable and co-Turing recognizable. This can be seen by running both deciders simultaneously.
As a result, is not Turing-recognizable.
Halting Problem
is undecidable by reduction to . Given , we can run and on simultaneously, returning appropriate results to create a decider for .
Examples
is undecidable also by reduction to . Given , modify such that accepts iff accepts and . Then, running on decides if accepts .
is undecidable. Given some , construct that accepts by default, and all strings iff accepts . Then is a decider for .
is undecidable, by reduction to . Let be a TM that rejects all inputs, and compare input to .
A linear bounded automaton is a Turing machine where the tape head cannot move off the portion containing the input. This means the set of possible configurations is finite.
An with states, symbols, has configurations given a tape of length . Thus is decidable, since we can simulate this many steps and before accepting or determining looping.
Rice’s Theorem is a nontrivial property if and for all , if and , then . Then is an undecidable language. This can be reduced to the halting problem.
WLOG assume machines that return an empty language are not included in . If they are, take instead. Let . Define a TM that and given , constructs a TM that does the following.
run on
run on and return this result
Let construct and return if . If halts, then this machine is equivalent to and accepts. If does not halt, then and rejects. decides the halting problem, giving a contradiction.