Ch 4 : Decidability

Question 1

Can all problems be solved by algorithms?

Answer 1

Absolutely not, thus this chapter.

Question 2

Why is knowing problems are unsolvable important?

Answer 2

to know when problems should be altered, simplified, approximated, or just plain appreciated.

Question 3

Why are we using languages to represent computational problems?

Answer 3

We already have the terminology setup… for example the acceptance problem for DFA’s of testing whether a particular DA accepts a string can be the language A.DFA.

Question 4

What does the language A.DFA contain?

Answer 4

The encodings of all DFA’s, together with the strings that the DFA’s accept.

Question 5

What is the formal defn of A.DFA?

Answer 5

{<b> | B is a DFA that accepts input string w}</b>

Question 6

What is the equivalence of language membership and computational problems

Answer 6

Testing whether DFA B accepts string w is the same as testing whether <b> is a member of the language A.DFA.</b>

Showing that a language is decidable is the same as showing that the computational problem is decidable.</b>

Question 7

Why, for decidability purposes, does it not matter whether we present Turing Machine with a DFA, NFA, or regular expression?

Answer 7

It can convert them all to DFA encoding, and then run the DFA decidability test on it.