Undecidable Languages - Easy Theory

Currently Playing: Decidable Languages NOT Closed Under Homomorphism

Here we show that decidable languages are not closed under homomorphism. We also show that the same languages ARE closed under inverse homomorphism. A homomorphism is a function h from a set A to a set B such that for any strings x, y in A, h(xy) = h(x)h(y); informally, this means that the function can "split up" a string into individual characters, apply the function to each, and concatenate the results. The homomorphism of a language L is the set of all strings h(x) where x is in L. An inverse homomorphism is the same as a homomorphism, but in reverse; a function h^(-1) applied to a language, which is the set of all strings x such that h(x) is in L - note that the order is swapped on h(x) and x here. Easy Theory Website: https://www.easytheory.org Discord: https://discord.gg/SD4U3hs If you like this content, please consider subscribing to my channel: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1 ▶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 many courses at several different universities, including several sections of undergraduate and graduate theory-level classes.