Understanding Recursive vs Recursively Enumerable Languages
Comparison between recursive and recursively enumerable languages in terms of Turing Machines acceptance, decidable languages, recognizable languages, and partial predicates. Explains the concepts with examples and how Turing Machines decide membership in languages.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Recursively Enumerable Languages A language is called Recursively Enumerable if there is a Turing Machine that accepts on any input within the language. Reminder: A language is called Recursive if there is a Turing Machine that accepts on any input within the language and rejects on any other input.
Recursive vs Recursively Enumerable Languages Recursive languages are also called Decidable Languages because a Turing Machine can decide membership in those languages (it can either accept or reject a string). Recursively Enumerable Languages are also called Recognizable because a Turing Machine can recognize a string in the language (accept it). It might not be able to decide if a string is not in the language since the machine might loop for that input.
Recursive Languages are also Recursively Enumerable Proof: If L is recursive then there is a Turing Machine M that decides membership in L: M accepts on x if x is in L M rejects on x if x is not in L By definition, M can recognize strings in the language (accept on those strings).
Partial Predicates Partial Predicates are predicates defined only for some input. We use the symbol to denote that some value is undefined Example: , 1 = y : 2 y N x = ( ) p x else
Recursively Enumerable Languages revisited Partially Computable Predicates: There is a Turing Machine that halts on the defined values and loops on the undefined. A language L is Recursively Enumerable if its characteristic function Lis partially computable, i.e. there is a Turing Machine that accepts for L= 1, rejects for L= 0 and loops for L= .
Predicate H is partially computable The partial predicate , 1 ( ) M M halts = ( ) I M , ( ) M M loops is partially computable. Run U , a slightly changed version of the Universal Turing machine U on input (<M>,<M>) (U should accept if U accepts or rejects, else it should loop).
A predicate that is not partially computable Consider the predicate , 0 , ( ) M M halts = ( ) I M ( ) M M loops This predicate is not partially computable (Intuition: there is no way that we can design a Turing Machine that halts for input <M> when M loops).
is not partially computable Assume that there was a Turing Machine that could partially compute . Idea: Run both machines U and on input (<M>,<M>). At some point one of them will halt: If U halts then accept if halts then reject. But this decides the H predicate. Contradiction! (Simulation of the concurrent running of U and can be performed using a 2-tape TM and performing one step of the computation of U and at a time interchangeably).
