Recursive vs Recursively Enumerable Languages
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:
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
χ
L
is 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
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
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).
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).
