Undecidable Languages - Easy Theory

Currently Playing: Acceptance for Turing Machines is Undecidable, but Recognizable

Here we show that the A_TM problem is undecidable and recognizable, which is asking if there is a decider for whether an arbitrary Turing Machine accepts an arbitrary input. The proof is by contradiction and diagonalization. What is a Turing Machine? It is a state machine that has a set of states, input, tape alphabet, a start state, exactly one accept state, and exactly one reject state. See https://www.youtube.com/watch?v=j0bIxPqlYLE&ab_channel=EasyTheory for more details. Easy Theory Website: https://www.easytheory.org GoFundMe: https://www.gofundme.com/f/easy-theory-video-studio Patreon: https://www.patreon.com/EasyTheoryYT Fourthwall: https://easy-theory-llc-shop.fourthwall.com Problem Solving channel: ​⁠ @easytheoryprobsolve If you like this content, please consider subscribing to my channel: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1