6
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 3
    $\begingroup$ I'd tell you, but I'm having trouble deciding what to write! ;) $\endgroup$
    – Carl Smotricz
    Commented Dec 6, 2009 at 15:52
  • 1
    $\begingroup$ Decidability is for languages, not machines. Languages that can be defined by NFAs are regular languages. All regular languages are decidable. Yes, as the "complexity" of the language grows (higher in the Chomsky hierarchy), some problems become undecidable. $\endgroup$
    – Mehrdad Afshari
    Commented Dec 6, 2009 at 15:55
  • $\begingroup$ :) These concepts make me really confused. I really need a simple examples to understand:) $\endgroup$
    – Marigi Maskere
    Commented Dec 6, 2009 at 15:56
  • $\begingroup$ You need to come up with a more focused question. $\endgroup$
    – Raphael
    Commented Jul 17, 2012 at 22:55

1 Answer 1

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.