Decidability and Undecidability Questions and Answers

Answer: D

The function is the Ackermann function.

The Ackermann function is total and computable, so it is (partially) recursive in the sense of the general recursive or mu-recursive functions. But it grows faster than every primitive recursive function, so it cannot be built using only composition and primitive recursion. It is the standard example of a recursive function that is not primitive recursive.

The other names are not standard examples in computability theory, so they are ruled out.

Answer: B

The undecidable problem is the halting problem for Turing machines.

Turing proved in 1936 that no algorithm can decide, for every machine and input, whether that Turing machine halts. The proof is by diagonalisation: a supposed decider could be used to build a machine that halts exactly when the decider says it does not.

The other three are decidable. Membership in a regular language is checked by running a DFA. Emptiness of a finite automaton is checked by seeing whether any accepting state is reachable. Two DFAs are equivalent if their minimised forms are the same.

Answer: C

The decidable problem is EQUIVALENCE OF DFA.

Whether two DFAs accept the same language can be decided: minimise both and compare them, or build a DFA for the symmetric difference of their languages and test it for emptiness, which is a simple reachability check.

The halting problem for Turing machines is the classic undecidable problem. Emptiness and equivalence of Turing machines are undecidable as well, by Rice's theorem, since each asks a non-trivial question about the language a TM accepts.

Answer: A

Statement S1 is correct: for a context free grammar there is an algorithm to decide whether the language is infinite, by checking for a cycle in the useful part of the grammar or by the pumping lemma. Statement S2 is not correct, since equivalence of two context free grammars is undecidable.

So S1 is correct and S2 is not, which is option A. Option B takes the undecidable problem as decidable, and options C and D deny S1, which has a known algorithm. Emptiness, finiteness and membership are decidable for context free languages, while equivalence, universality and ambiguity are not.