Decidability of Machines

Question

Hello, I cannot understand decidability really well. I have been reading from books and internet, but I am little bit confused. According to the book (as I understood), we can decide on decidability of a problem by constructing Turing Machines. Let us say that we want to decide whether an NFA is a decidable language. First, we need to construct a Turing Machine that accepts if the run on w in NFA ends in accept state, otherwise Turing Machine rejects. According to this definition, I can construct any Turing Machine that can decide every NFA. As a result, I can say that every NFA that can be constructed is decidable. Is this true ?

Additionally, I realized that we cannot decide whether two Context Free Grammars produce same languages. However, we can decide whether two NFA produce same language. Therefore, can we conclude that as our machines get complicated, some of the problems get harder to decide ?

I mean lets take an example. Let us say that there is an NFA that accepts some string w whose length is a composite number. I think that this is a decidable problem.

As you can see that I am little bit confused with these concepts. It will be a lot better for me to go over an example, because it is difficult for me to understand only from conceptual explanations.

Answer 1

As a result, I can say that every NFA that can be constructed is decidable. Is this true?

Yes. An NFA can be converted to a deterministic finite automaton, and that can simply be run to decide the output.

However, is it possible to find a Turing Machine that can accept w whose length is composite number?

Yes, this is possible. It follows from the fact that it can be done in any old Turing-complete programming language, hence also on a TM.

Is it possible to construct a CFG that accepts this w?

I doubt it. Maybe there is a proof, but I do not see it right away.

Most problems you'll encounter in practice are decidable, because you can come up with an algorithm to decide the answer. If you want an example of an undecidable problem, have a look at this list on Wikipedia.