731 views
2 votes
2 votes

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 $2$:Does a single instance of "turing machine's halting problem" is decidable?
As I given above example, I think this is also Undecidable.

If I am doing something wrong then please tell me what is really mean by "Domain of a problem" and "single instance of turing machine's halting problem"? 

Please log in or register to answer this question.

Related questions

3 votes
3 votes
1 answer
1
Vinil asked Sep 16, 2017
5,033 views
No of states in finite automata whose string length is divisible by 3 or8?
0 votes
0 votes
1 answer
3