322 views
2 votes
2 votes

why B? why not C

1 Answer

0 votes
0 votes
My idea would be to check if any TM has empty language or not. Now if I can prove in some way that its not possible to find whether any TM has empty language or not then its also proved that this equivalence is undecidable. So I would encode a machine_A to halt on every TM A which accepts iff TM A  terminates on input A.

And Therefore, deciding for all A whether machine_A accepts words or not, is the same as deciding for all Turing machines A whether it terminates on input A or not — and this is exactly the halting problem. Also since halting problem is undecidable, thus it is also undecidable.
edited by

Related questions

2 votes
2 votes
1 answer
1
Souvik33 asked Nov 23, 2022
317 views
If L and $L^{c}$ both are CFL, the L must be DCFL a. TRUE b.FALSE
3 votes
3 votes
1 answer
2
0 votes
0 votes
1 answer
3
amitqy asked Dec 15, 2018
401 views
0 votes
0 votes
0 answers
4
amitqy asked Nov 21, 2018
477 views
What is partial language?