Here we go over a GATE exam problem about a language of Turing Machines that accept some string of length 2020. We then classify this language as being undecidable but recognizable. The proof of undecidability is supposing a decider for it exists, then obtaining a decider for A_TM from that, which we know cannot exist. The proof of recognizable comes from "brute force" parallel simulation of all strings of length 2020, and accepting if any such string is accepted.
If you like this content, please consider subscribing to my channel: ru-vid.com/show-UC3VY6RTXegnoSD_q446oBdg
▶ADDITIONAL QUESTIONS◀
1. Could we have applied Rice's Theorem to this problem?
2. What can we say about the complement of L?
▶SEND ME THEORY QUESTIONS◀
ryan.e.dougherty@icloud.com
▶ABOUT ME◀
I am a professor of Computer Science, and am passionate about CS theory. I have taught over 12 courses at Arizona State University, as well as Colgate University, including several sections of undergraduate theory.
16 апр 2020
