875 views
1 votes
1 votes

4 Answers

Best answer
6 votes
6 votes
few machines might not halt on X. then we cant say anything abt X. neither yes nor No
but when every TM accepts x, we can say that "yes,x is accepted by all TMs"
we are able to say "yes" for yes cases, but unable to say "No" when any TM doesnt halt on x . so recursively ennumerable but not recursive
selected by
7 votes
7 votes

Actually here the catch is :

Set of Turing Machines : M1 , M2 , M3 ,............, Mn

Hence it is a finite set as mentioned in the question as n will be some finite number..

So doing check on finite no of machines will take finite amount of time provided all M1 through Mn will halt on the given string w..But say if one TM does not accept it then it may or may not halt..

Thus the given problem is RE but not REC.. 

If the problem were :

Set of all TMs and whether each TM halts on input w

Then the problem would have been Non RE.. 

0 votes
0 votes

Halting problem is Undecidable.

Hence, there is no Total turing machine exists which can give correct answer each time for the halting problem.

Only non-halting turing machine(aka Turing machine) which accepts RE languages exist for halting problem.

non-halting Turing machines accept RE languages but Total turing machines accept Recursive languages.

Hence, it is RE but not recursive.

https://www.tutorialspoint.com/automata_theory/turing_machine_halting_problem.htm

0 votes
0 votes
The reason why L is RE and not REC is because even though L halts we don't know if L' will also halt. For REC both should halt. If l and L' halts on all TM only then it is REC.
edited by

Related questions

1 votes
1 votes
2 answers
1
Lucky sunda asked Feb 7, 2017
605 views
0 votes
0 votes
1 answer
2
smartmeet asked Feb 8, 2017
498 views
Which of the following statements is FALSE?(A) Each thread has own stack(B) Starvation implies deadlock(C) Smaller page size increases the page table size(D) User level p...
0 votes
0 votes
3 answers
3
Lucky sunda asked Feb 7, 2017
701 views
According to me option B is correct.
4 votes
4 votes
3 answers
4
smartmeet asked Feb 7, 2017
777 views
Given TMs and L = {x/Every halts on input x } which of the following is true about L?(A) L is recursively enumerable but not recursive(B) L is Recursive but not Context...