whether it accepted all inputs. This is where we proved the non-existence of M T
ID: 3838117 • Letter: W
Question
whether it accepted all inputs. This is where we proved the non-existence of M To some extent, this isn't too surprising since there are infinitely many possible input strings, and it would never be possible to test them all. What might be more surprising is that it's also undecidable whether a TM accepts any single input string, even the empty string. So let Le (M) I M accepts E Prove that Le s undecidable. In other words, prove that there can be no such TM ME which accepts all those machines that accept the empty string and which rejects all those that do not accept the empty string.Explanation / Answer
Here is one proof :
- Lets say L is language which accepts only null staring and there is some turing machine M for L which accepts Null string only and reject all other strings .
- Then it is a decidable problem and L becomes a decidable language.
- If L is decidable then L' also has to be decidable. Where L' is complement of language L.
- Complement of Langyage L = L' = language of all strings.
- Since L' is decidable there has to be a turing machine which accepts all the string.
- But we can not have any such turing machine which can accept all strings as there are infinitely many possible input strings and it would never be possible to test them all.
- So L' is not a decidable language.
- Hence our assumption is wrong. L can not be decidable. L is undecidable.
Hence There is no such turing machine which can accept empty string only.
If you have any doubts, you can ask in comment section.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.