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

Improve this question
$\endgroup$
4
  • $\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
    Commented Oct 23, 2014 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
    Commented Oct 23, 2014 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
    Commented Oct 23, 2014 at 18:02
  • $\begingroup$ @YuvalFilmus Thanks for the links will look into them :) $\endgroup$
    – Swathi
    Commented Oct 23, 2014 at 18:04

1 Answer 1

Reset to default
7
$\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.

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.

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