1
$\begingroup$

Question no:$1$

"Any problem whose domain is finite is always Decidable"

lets take a TM,$M$ and finite domain of problem i.e. finite set of strings for eg. {$a,abaa,bba$}, Now the problem "whether $M$ accepts these set of strings or not is decidable or not?"

What I think is, this is Undecidable problem because, if $M$ loops forever any of these string then we not determine whether turing machine accept it or not.so according to this logic above statement is false.

Question no:$2$

Does a single instance of "turing machine's halting problem" is decidable?
As I given above example, I think this is also Undecidable.

Improve this question
$\endgroup$
1
  • $\begingroup$ For your second question (and, by extension, your first), if the problem you intend is "Does this TM halt on this input?" then this single-instance problem is decidable. There are two deciders, one that answers "yes" and another that answers "no". We don't know which one is the right one, but that doesn't matter: a problem is decidable if there is a decider for it and in any case we have that. $\endgroup$
    – Rick Decker
    Commented Nov 12, 2017 at 20:05

1 Answer 1

Reset to default
2
$\begingroup$

It's not so clear what is "a problem whose domain is finite". Let me assume that what is meant by this is a finite language. Every finite language is decidable. The Turing machine compares the input to each word in the language, accepts if it finds a match, and rejects otherwise.

This answers your first question. Your second question is a special case of the first one.

Improve this answer
$\endgroup$
4
  • $\begingroup$ sir,If we have to decide the membership of a string for a language then your method will work.But,lets take a turing machine $M$ and a finite language $L$={a,b,aa,bb,ab,ba} then, problem if $M$ accepts $L$ is Undecidable because of looping nature of turing machine.Then How can we say that above statement is true.If I am misunderstanding something about the above statement then please correct me. $\endgroup$
    – Reena Kandari
    Commented Nov 12, 2017 at 11:50
  • 1
    $\begingroup$ Your misunderstanding is about the meaning of the phrase Any problem whose domain is finite is always Decidable. It has the meaning in my answer rather than the meaning in your comment. $\endgroup$
    – Yuval Filmus
    Commented Nov 12, 2017 at 12:22
  • $\begingroup$ "A language is Decidable" does it mean that there exists a TM which can halt on any string of this language or in other words "there is a membership algorithm for this language"? what does it exactly mean. $\endgroup$
    – Reena Kandari
    Commented Nov 12, 2017 at 12:57
  • 1
    $\begingroup$ A language is decidable if some Turing machine decides it. $\endgroup$
    – Yuval Filmus
    Commented Nov 12, 2017 at 14:31

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.