[go: up one dir, main page]
Scribd
Upload
14K views8 pages

Recursively Enumerable Languages

- Recursively enumerable (RE) languages are those for which there exists a Turing machine that accepts any string in the language, but may not halt on strings not in the language. Recursive languages are decidable - a Turing machine can accept or reject any string. - RE languages are also called recognizable as a machine can recognize strings within the language by accepting. Recursive languages are a subset of RE languages. - A language is RE if its characteristic function is partially computable by a Turing machine that halts on defined values and loops on undefined values.

Uploaded by

Tharun Karimilla
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
14K views8 pages

Recursively Enumerable Languages

- Recursively enumerable (RE) languages are those for which there exists a Turing machine that accepts any string in the language, but may not halt on strings not in the language. Recursive languages are decidable - a Turing machine can accept or reject any string. - RE languages are also called recognizable as a machine can recognize strings within the language by accepting. Recursive languages are a subset of RE languages. - A language is RE if its characteristic function is partially computable by a Turing machine that halts on defined values and loops on undefined values.

Uploaded by

Tharun Karimilla
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 8

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  N : x  2 y
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 χ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
 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


, M ( M ) halts
I ( M  )  
0, 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).

You might also like