3
$\begingroup$

Hopefully this is not a duplicate

How do I prove a Language L={a,b,c} is decidable or not

I read somewhere that if a turing machine accepts a language and halts on every input string then the language is decidable.

Having said that how do i design / prove that a turing machine accepts {a b c}

I am new to concepts of automata and compelexity so please don't kill me if this is too basic for a question

$\endgroup$
  • $\begingroup$ By definition, a language is decidable if there is a Turing machine that accepts it, that is, halts on all inputs, and answers "Yes" on words in the language, "No" on words not in the language. $\endgroup$ – Yuval Filmus Oct 23 '14 at 17:58
  • $\begingroup$ @YuvalFilmus how do i prove the above statement, can you help me with an example on how a turing machine will accept the language, I am too naive and trying to get a grip $\endgroup$ – Swathi Oct 23 '14 at 17:59
  • 3
    $\begingroup$ Your textbook can probably help you, as are many online resources. What resources are most helpful for you depends on your level. You can start with www3.cs.stonybrook.edu/~cse350/slides/turing1.pdf and www3.cs.stonybrook.edu/~cse350/slides/turing2.pdf. $\endgroup$ – Yuval Filmus Oct 23 '14 at 18:02
  • $\begingroup$ @YuvalFilmus Thanks for the links will look into them :) $\endgroup$ – Swathi Oct 23 '14 at 18:04
4
$\begingroup$

By definition, a language is decidable if there exists a Turing machine that accepts it, that is, halts on all inputs, and answers "Yes" on words in the language, "No" on words not in the language. Therefore one way of showing that a language is decidable is by describing a Turing machine that accepts it.

There are many offline and online resources on Turing machines. For example, here are some introductory slides on Turing machines: part 1, part 2.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.