5
$\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.

$\endgroup$

migrated from stackoverflow.com Jul 17 '12 at 19:40

This question came from our site for professional and enthusiast programmers.

  • 3
    $\begingroup$ I'd tell you, but I'm having trouble deciding what to write! ;) $\endgroup$ – Carl Smotricz Dec 6 '09 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 Dec 6 '09 at 15:55
  • $\begingroup$ :) These concepts make me really confused. I really need a simple examples to understand:) $\endgroup$ – Marigi Maskere Dec 6 '09 at 15:56
  • $\begingroup$ You need to come up with a more focused question. $\endgroup$ – Raphael Jul 17 '12 at 22:55
5
$\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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy