FIT2014 Theory of Computation Lecture 23 Recursively enumerable languages
Monash University
Faculty of Information Technology
-Autumn
Festival!
中秋节快乐
[your
greetings
here]
FIT2014 Theory of Computation
Lecture 23
Recursively enumerable languages
slides by
COMMONWEALTH OF AUSTRALIA
Copyright Regulations 1969
Warning
This material has been reproduced and communicated to you by or on behalf of Monash University
in accordance with s113P of the Copyright Act 1968 (the Act).
The material in this communication may be subject to copyright under the Act.
Any further reproduction or communication of this material by you may be the subject of copyright protection under the Act.
Do not remove this notice.
1 / 22
Overview
I recursively enumerable (r.e.) languages
I relationship with decidability
I enumerators
I non-r.e. languages
2 / 22
Decidability
Recall:
A language L is decidable if and only if there exists a Turing machine T such that
Accept(T ) = L
Reject(T ) = L
Loop(T ) = ∅.
Reminder: L = Σ∗ \ L, where Σ is the alphabet.
3 / 22
Recursively enumerable languages: definition
A language L is recursively enumerable if there exists a Turing machine T such that
Accept(T ) = L
Strings outside L may be rejected, or may make T loop forever.
4 / 22
Recursively enumerable: synonyms
recursively enumerable (r.e.)
= computably enumerable
= partially decidable
= Turing recognisable (used in Sipser)
= type 0 (in Chomsky hierarchy)
= computable
. . . but risk of confusion, as “computable” is sometimes used for “decidable”.
5 / 22
Decidable versus r.e.
Every decidable language is recursively enumerable.
Is every recursively enumerable language decidable?
Consider:
HALT = {T : T halts, if input is T}
This is the language corresponding to the Halting Problem.
We know it’s not decidable.
Is it recursively enumerable?
6 / 22
Decidable versus r.e.
Let M be a Turing machine which takes, as input, a Turing machine T and
I simulates what happens when T is run with itself as its input.
I If T stops (in any state), M accepts.
Here, M could be obtained by modifying a UTM.
Accept(M) = HALT
Reject(M) = ∅
Loop(M) = HALT
7 / 22
Decidable versus r.e.
So HALT is recursively enumerable.
So some recursively enumerable languages are not decidable.
Consider the list of undecidable languages given in Lecture 22.
Which ones are recursively enumerable?
8 / 22
Decidable versus r.e.
Theorem.
A language is decidable if and only if both it and its complement are r.e.
Proof.
( =⇒ )
Let L be any decidable language.
We have seen that every decidable language is r.e. So L is r.e.
Now, the complement of a decidable language is also decidable.
(See Lecture 20, comments on closure properties of the class of decidable languages.)
So L is also decidable, and therefore also r.e.
So L and L are both r.e.
9 / 22
Decidable versus r.e.
( ⇐= )
Let L be any language such that both L and L are both r.e.
Since they are each r.e., there exist Turing machines M1 and M2 such that
Accept(M1) = L
Accept(M2) = L.
Note, each of these TMs might loop forever for inputs they don’t accept.
Construct a new Turing machine M ′ that simulates both M1 and M2:
Input: x
Repeatedly:
Do one step of M1. If it accepts, then Accept.
Do one step of M2. If it accepts, then Reject.
10 / 22
Decidable versus r.e.
M ′ is a decider:
I every string belongs to either L or L,
I therefore is accepted by either M1 or M2,
I therefore will eventually be either accepted or rejected by M ′.
Furthermore, M ′ accepts x if and only if M1 accepts x .
So M ′ is a decider for L.
So L is decidable.
11 / 22
A non-r.e. language
Is every language recursively enumerable?
Consider:
HALT = {T : T loops forever, if input is T}
Assume HALT is r.e.
We already know that HALT is r.e.
So, both HALT and its complement are r.e.
Therefore, by the previous theorem, HALT is decidable.
Contradiction!
Therefore HALT is not r.e.
12 / 22
Enumerators
Definition
An enumerator is a Turing machine which outputs a sequence of strings.
This can be a finite or infinite sequence.
If it’s infinite, then the enumerator will never halt.
It never accepts or rejects; it just keeps outputting strings, one after another.
I If the sequence is finite, then the enumerator may stop once it has finished outputting.
But the state it enters doesn’t matter.
13 / 22
Enumerators
Definition
A language L is enumerated by an enumerator M if
L = {all strings in the sequence outputted by M}
Members of L may be outputted in any order by M, and repetition is allowed.
Theorem
A language is recursively enumerable if and only if it is enumerated by some enumerator.
14 / 22
Enumerators and r.e. languages
Theorem
A language is recursively enumerable if and only if it is enumerated by some enumerator.
Proof.
( ⇐= )
Let L be a language, and let M be an enumerator for it.
Construct a Turing machine M ′ as follows:
Input: a string x
Simulate M, and for each string y it generates:
Test if x = y . If so, accept; otherwise, continue.
A string x is accepted by M ′ if and only if it is in L.
So Accept(M ′) = L. So L is r.e.
15 / 22
Enumerators and r.e. languages
( =⇒ ) Let L be r.e. Then there is a TM M such that Accept(M) = L. Take all
strings, in order:
ε, a, b, aa, ab, ba, bb, aaa, aab, aba, . . .
Simulate the execution of M on each of these strings, in parallel.
As soon as any of them stops and accepts its string,
we pause our simulation, output that string, and then resume the simulation.
CAREFUL:
Infinitely many executions to simulate, but we only have finite time!
How do we schedule all these simulations?
16 / 22
Enumerators and r.e. languages
Denote the strings by x1, x2, . . . , xi , . . .
Algorithm:
For each k = 1, 2, . . .
For each i = 1, . . . , k :
Simulate the next step of the execution of M on xi
(provided that execution hasn’t already stopped).
If this makes M accept, then
output xi and skip i in all further iterations;
else if this makes M reject, then
output nothing, and skip i in all further iterations.
17 / 22
Enumerators and r.e. languages
This algorithm can be implemented by a Turing machine.
Any string accepted by M will eventually be outputted.
So this is an enumerator for L.
This result explains the term “recursively enumerable” (and “computably enumerable”).
It also explains why r.e. languages are sometimes called computable, since
there is a computer that can compute all its members (i.e., can generate them all).
18 / 22
Exercises
Theorem.
A language L is r.e. if and only if
there is a decidable two-argument predicate P such that
x ∈ L ⇐⇒ ∃y : P(x , y).
This P is a verifier :
if you are given y then you can use P to verify that x is in L (if it is).
But it may be hard to find such a y .
Theorem.
If K ≤m L and L is r.e. then K is r.e.
19 / 22
Recursively enumerable languages
regular
CFLs
r.e.
Decidable
HALTHALT
20 / 22
Recursively enumerable languages
regular
CFLs
r.e.co-r.e.
Decidable
HALTHALT
21 / 22
Revision
I definition of recursively enumerable languages
I relationship between decidability and recursive enumerability
I enumerators and their relationship with r.e. languages
I a language that is r.e. but not decidable, with proof
I a language that is not r.e., with proof
Reading: Sipser, pp. 170, 209–211.
Preparation: Sipser, pp. 275–286.
22 / 22