Recursive and Recursively Enumerable Languages
undefined
1
Undecidability
Reading: Chapter 8 & 9
2
Decidability vs. Undecidability
There are two types of TMs (based on halting):
(
Recursive
)
T
M
s
t
h
a
t
a
l
w
a
y
s
h
a
l
t
,
n
o
m
a
t
t
e
r
a
c
c
e
p
t
i
n
g
o
r
n
o
n
-
a
c
c
e
p
t
i
n
g
D
E
C
I
D
A
B
L
E
P
R
O
B
L
E
M
S
(
Recursively enumerable
)
T
M
s
t
h
a
t
a
r
e
g
u
a
r
a
n
t
e
e
d
t
o
h
a
l
t
o
n
l
y
o
n
a
c
c
e
p
t
a
n
c
e
.
I
f
n
o
n
-
a
c
c
e
p
t
i
n
g
,
i
t
m
a
y
o
r
m
a
y
n
o
t
h
a
l
t
(
i
.
e
.
,
c
o
u
l
d
l
o
o
p
f
o
r
e
v
e
r
)
.
U
n
d
e
c
i
d
a
b
i
l
i
t
y
:
Undecidable problems are those that are
not
recursive
3
Recursive, RE, Undecidable languages
Regular
(DFA)
Context-
free
(PDA)
Context
sensitive
Recursive
Recursively
Enumerable (RE)
Non-RE Languages
(all other languages for which
no TMs can be built)
LBA
TMs that always halt
TMs that may or
may not halt
No TMs exist
“
U
n
d
e
c
i
d
a
b
l
e
”
p
r
o
b
l
e
m
s
“
D
e
c
i
d
a
b
l
e
”
p
r
o
b
l
e
m
s
4
Recursive Languages &
Recursively Enumerable (RE)
languages
Any TM for a
Recursive
language is going to
look like this:
Any TM for a
Recursively Enumerable
(RE)
language is going to look like this:
M
w
“
a
c
c
e
p
t
”
“
r
e
j
e
c
t
”
M
w
“
a
c
c
e
p
t
”
5
Closure Properties of:
- the Recursive language
class, and
- the Recursively Enumerable
language class
6
Recursive Languages are closed
under
complementation
If L is Recursive, L is also Recursive
M
w
“accept”
“reject”
w
7
Are Recursively Enumerable
Languages closed under
complementation
?
(NO)
If L is RE, L need not be RE
M
w
“accept”
w
?
?
Recursive Langs are closed
under Union
Let M
u
= TM for L
1
U L
2
M
u
construction:
1.
Make 2-tapes and
copy input w on both
tapes
2.
Simulate M
1
on tape 1
3.
Simulate M
2
on tape 2
4.
If either M
1
or M
2
accepts, then M
u
accepts
5.
Otherwise, M
u
rejects.
8
M
u
Recursive Langs are closed
under Intersection
Let M
n
= TM for L
1
L
2
M
n
construction:
1.
Make 2-tapes and
copy input w on both
tapes
2.
Simulate M
1
on tape 1
3.
Simulate M
2
on tape 2
4.
If M
1
AND M
2
accepts,
then M
n
accepts
5.
Otherwise, M
n
rejects.
9
M
n
10
Other Closure Property
Results
Recursive languages are also closed under:
Concatenation
Kleene closure (star operator)
Homomorphism, and inverse homomorphism
RE languages are closed under:
Union, intersection, concatenation, Kleene closure
RE languages are
not
closed under:
complementation
11
“Languages” vs. “Problems”
A “language” is a set of strings
Any “problem” can be expressed as a set of all
strings that are of the form:
“<input, output>”
==> Every problem also corresponds to a
language!!
Think of the language for a “problem” == a
verifier
for the problem
e.g., Problem (a+b) ≡ Language of strings of the form { “a#b, a+b” }12
T
h
e
H
a
l
t
i
n
g
P
r
o
b
l
e
m
A
n
e
x
a
m
p
l
e
o
f
a
r
e
c
u
r
s
i
v
e
e
n
u
m
e
r
a
b
l
e
p
r
o
b
l
e
m
t
h
a
t
i
s
a
l
s
o
u
n
d
e
c
i
d
a
b
l
e
13
Regular
(DFA)
Context-
free
(PDA)
Context
sensitive
Recursive
Recursively
Enumerable (RE)
Non-RE Languages
T
h
e
H
a
l
t
i
n
g
P
r
o
b
l
e
m
x
14
What is the Halting Problem?
Definition of the “halting problem”:
Does a givenTuring Machine M halt on
a given input w?
Machine
M
Input w
15
The Universal Turing Machine
G
i
v
e
n
:
T
M
M
&
i
t
s
i
n
p
u
t
w
Aim:
Build another TM called “H”, that will output:
“
accept
” if M accepts w, and
“reject” otherwise
An algorithm for H:
Simulate M on w
H(<M,w>) =
accept
, if
M
accepts w
reject
,
if M does does not accept w
A Turing Machine simulator
Question:
If M does
not
halt on w, what will happen to H?
Implies: H is in RE
16
A Claim
Claim:
No H that is always guaranteed
to halt, can exist!
Proof:
(Alan Turing, 1936)
By contradiction, let us assume H exists
17
HP Proof (step 1)
L
e
t
u
s
c
o
n
s
t
r
u
c
t
a
n
e
w
T
M
D
u
s
i
n
g
H
a
s
a
s
u
b
r
o
u
t
i
n
e
:
On input <M>:
1.
Run H on input <M, <M> >; //(i.e., run M on M itself)
2.
Output the
opposite
of what H outputs;
H
<M>
D
Therefore, if H exists
D also should exist.
But can such a D exist?
(if not, then H also cannot exist)
18
HP Proof (step 2)
The notion of inputing “<M>” to M itself
A program can be input to itself (e.g., a compiler is a
program that takes any program as input)
Now, what happens if D is input to itself?
A
c
o
n
t
r
a
d
i
c
t
i
o
n
!
!
!
=
=
>
N
e
i
t
h
e
r
D
n
o
r
H
c
a
n
e
x
i
s
t
.
19
Of Paradoxes & Strange
Loops
A fun book for further reading:
“
G
o
d
e
l
,
E
s
c
h
e
r
,
B
a
c
h
:
A
n
E
t
e
r
n
a
l
G
o
l
d
e
n
B
r
a
i
d
”
b
y
D
o
u
g
l
a
s
H
o
f
s
t
a
d
t
e
r
(
P
u
l
i
t
z
e
r
w
i
n
n
e
r
,
1
9
8
0
)
E.g., Barber’s paradox, Achilles & the Tortoise (Zeno’s paradox)
MC Escher’s paintings
20
The Diagonalization Language
E
x
a
m
p
l
e
o
f
a
l
a
n
g
u
a
g
e
t
h
a
t
i
s
n
o
t
r
e
c
u
r
s
i
v
e
e
n
u
m
e
r
a
b
l
e
(
i
.
e
,
n
o
T
M
s
e
x
i
s
t
)
21
Regular
(DFA)
Context-
free
(PDA)
Context
sensitive
Recursive
Recursively
Enumerable (RE)
Non-RE Languages
T
h
e
H
a
l
t
i
n
g
P
r
o
b
l
e
m
T
h
e
D
i
a
g
o
n
a
l
i
z
a
t
i
o
n
l
a
n
g
u
a
g
e
x
x
22
A Language about TMs &
acceptance
Let L be the language of all strings
<M,w> s.t.:
1.
M is a TM (coded in binary) with input
alphabet also binary
2.
w is a binary string
3.
M accepts input w.
23
Enumerating all binary strings
Let w be a binary string
Then 1w
i, where i is some integer
E.g., If w=
, then i=1;
If w=0, then i=2;
If w=1, then i=3; so on…
If 1w
i, then call w as the i
th
word or i
th
binary
string, denoted by w
i
.
=
=
>
A
c
a
n
o
n
i
c
a
l
o
r
d
e
r
i
n
g
o
f
a
l
l
b
i
n
a
r
y
s
t
r
i
n
g
s
:
{
,
0
,
1
,
0
0
,
0
1
,
1
0
,
1
1
,
0
0
0
,
1
0
0
,
1
0
1
,
1
1
0
,
…
.
.
}
{w
1
,
w
2
,
w
3
,
w
4
,
…
.
w
i
,
…
}
24
Any TM M can also be binary-
coded
M = { Q, {0,1},
,
, q
0
,B,F
}
Map all states, tape symbols and transitions to
integers (==>binary strings)
(q
i
,X
j
) = (q
k
,X
l
,D
m
) will be represented as:
==> 0
i
1 0
j
1 0
k
1 0
l
1 0
m
Result:
Each TM can be written down as a
long binary string
==> Canonical ordering of TMs:
{M1
, M
2
, M
3
, M
4
, …. M
i
, … }
25
The Diagonalization Language
L
d
= { wi
| w
i
L(M
i
) }
The language of all strings whose corresponding
machine does
not
accept itself (i.e., its own code)
i
j
…
.
.
.
diagonal
•
Table:
T[i,j] = 1, if M
i
accepts w
j
= 0, otherwise.
(input word w)
(TMs)
•
M
a
k
e
a
n
e
w
l
a
n
g
u
a
g
e
c
a
l
l
e
d
L
d
=
{w
i
|
T
[
i
,
i
]
=
0
}
26
L
d
is not RE (i.e., has no TM)
Proof (by contradiction):
Let M be the TM for L
d
==> M has to be equal to some M
k
s.t.
L(M
k
) = L
d
==> Will w
k
belong to L(M
k
) or not?
1.
If w
k
L(M
k
) ==> T[k,k]=1 ==>
w
k
L
d
2.
If w
k
L(M
k
) ==> T[k,k]=0 ==>
w
k
L
d
A contradiction either way!!
27
Why should there be
languages that do not have
TMs?
We thought TMs can solve
everything!!
28
Non-RE languages
Regular
(DFA)
Context-
free
(PDA)
Context
sensitive
Recursive
Recursively
Enumerable (RE)
Non-RE Languages
How come there are languages here?
(e.g., diagonalization language)
29
One Explanation
T
h
e
r
e
a
r
e
m
o
r
e
l
a
n
g
u
a
g
e
s
t
h
a
n
T
M
s
By pigeon hole principle:
==> some languages cannot have TMs
But how do we show this?
Need a way to “
count & compare
” two infinite
sets (languages and TMs)
30
How to count elements in a
set?
Let A be a set:
If A is finite ==> counting is trivial
If A is infinite ==> how do we count?
And, how do we compare two infinite sets by
their size?
31
Cantor’s definition of set “size”
for infinite sets (1873 A.D.)
Let N = {1,2,3,…}(all natural numbers)
Let E = {2,4,6,…}(all even numbers)
Q) Which is bigger?
A) Both sets are of the same size
“
C
o
u
n
t
a
b
l
y
i
n
f
i
n
i
t
e
”
Proof:
Show by one-to-one, onto set correspondence from
N ==> E
n
1
2
3
.
.
.
f(n)
2
4
6
.
.
.
i.e, for every element in N,
there is a unique element in E,
and vice versa.
32
Example #2
Let Q be the set of all rational numbers
Q = { m/n | for all m,n
N
}
Claim:
Q is also countably infinite; => |Q|=|N|
33
U
n
c
o
u
n
t
a
b
l
e
s
e
t
s
Example:
Let R be the set of all real numbers
Claim:
R is uncountable
n
1
2
3
4
.
.
.
f(n)
3 .
1
4 1 5 9 …
5 . 5
5
5 5 5 …
0 . 1 2
3
4 5 …
0 . 5 1 4
3
0 …
E.g. x = 0 . 2 6 4 4 …
Build x s.t. x cannot possibly
occur in the table
Really, really big sets!
(even bigger than countably infinite sets)
34
Therefore, some languages
cannot have TMs…
The set of all TMs is countably infinite
The set of all Languages is uncountable
==> There should be some languages
without TMs ( by PHP)
35
The problem reduction
technique, and reusing other
constructions
36
Languages that we know
about
Language of a Universal TM (“UTM”)
L
u
= { <M,w> | M accepts w }
Result:
L
u
is in RE but not recursive
Diagonalization language
L
d
= { wi
| M
i
does not accept w
i
}
Result:
L
d
is non-RE
37
TMs that accept non-empty
languages
L
ne
= { M | L(M) ≠
}
L
ne
is RE
Proof:
(build a TM for L
ne
using UTM)
UTM
M
“accept”
“accept”
N
o
n
-
d
e
t
e
r
m
i
n
i
s
t
i
c
S
i
m
u
l
a
t
o
r
f
o
r
L
n
e
M
Guess w
38
TMs that accept non-empty
languages
L
ne
is not recursive
Proof:
(“
Reduce
” L
u
to L
ne
)
Idea:
M accepts w if and only if L(M’) ≠
M
ne
<M,w>
“accept”
“accept”
L
u
M’
Transformation
function
L
n
e
39
Reducability
To prove:
Problem P
1
is undecidable
Given/known:
Problem P
2
is undecidable
Reduction idea:
1.
“Reduce” P
2
to P
1
:
Convert P
2
’s input instance to P
1
’s input instance s.t.
i)
P
2
decides only if P
1
decides
2.
Therefore, P
2
is decidable
3.
A contradiction
4.
Therefore, P
1
has to be undecidable
40
The Reduction Technique
Construct
yes
no
Decide
P
1
instance
P
2
instance
Conclusion:
If we could solve P
1
, then we can solve P
2
as well
Reduce P
2
to P
1
:
Note:
not same as
P
1
==> P
2
41
Summary
Problems vs. languages
Decidability
Recursive
Undecidability
Recursively Enumerable
Not RE
Examples of languages
The diagonalization technique
Reducability
Cpt S 317: Spring 2009
School of EECS, WSU
Exploring the concepts of decidability and undecidability in computer science, specifically focusing on Recursive and Recursively Enumerable (RE) languages. Recursive languages always halt, while RE languages may or may not halt, showcasing the differences between decidable and undecidable problems. The closure properties of Recursive and RE languages under complementation and union are discussed, shedding light on their computational complexity.
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
Undecidability Reading: Chapter 8 & 9 1
Decidability vs. Undecidability There are two types of TMs (based on halting): (Recursive) TMs that always halt, no matter accepting or non- accepting DECIDABLE PROBLEMS (Recursively enumerable) TMs that are guaranteed to halt only on acceptance. If non-accepting, it may or may not halt (i.e., could loop forever). Undecidability: Undecidable problems are those that are not recursive 2
Recursive, RE, Undecidable languages No TMs exist TMs that always halt LBA TMs that may or may not halt Non-RE Languages (all other languages for which no TMs can be built) Enumerable (RE) Recursively Context- Regular (DFA) sensitive Context Recursive free (PDA) Undecidable problems Decidable problems 3
Recursive Languages & Recursively Enumerable (RE) languages Any TM for a Recursive language is going to look like this: accept w M reject Any TM for a Recursively Enumerable (RE) language is going to look like this: accept w M 4
Closure Properties of: - the Recursive language class, and - the Recursively Enumerable language class 5
Recursive Languages are closed under complementation If L is Recursive, L is also Recursive M accept accept w M w reject reject 6
Are Recursively Enumerable Languages closed under complementation? (NO) If L is RE, L need not be RE M ? accept accept w M w reject ? 7
Recursive Langs are closed under Union Let Mu = TM for L1 U L2 Mu construction: Make 2-tapes and copy input w on both tapes Simulate M1 on tape 1 Simulate M2 on tape 2 If either M1 or M2 accepts, then Mu accepts Otherwise, Mu rejects. Mu accept M1 1. reject OR w accept M2 2. reject 3. 4. 5. 8
Recursive Langs are closed under Intersection Let Mn = TM for L1 L2 Mn construction: Make 2-tapes and copy input w on both tapes Simulate M1 on tape 1 Simulate M2 on tape 2 If M1 AND M2 accepts, then Mn accepts Otherwise, Mn rejects. Mn accept M1 1. reject AND AND w accept M2 2. reject 3. 4. 5. 9
Other Closure Property Results Recursive languages are also closed under: Concatenation Kleene closure (star operator) Homomorphism, and inverse homomorphism RE languages are closed under: Union, intersection, concatenation, Kleene closure RE languages are not closed under: complementation 10
Languages vs. Problems A language is a set of strings Any problem can be expressed as a set of all strings that are of the form: <input, output> e.g., Problem (a+b) Language of strings of the form { a#b, a+b } ==> Every problem also corresponds to a language!! Think of the language for a problem == a verifier for the problem 11
The Halting Problem An example of a recursive enumerable problem that is also undecidable 12
The Halting Problem Non-RE Languages Enumerable (RE) x Recursively Context- Regular (DFA) sensitive Context Recursive free (PDA) 13
What is the Halting Problem? Definition of the halting problem : Does a givenTuring Machine M halt on a given input w? Input w Machine M 14
A Turing Machine simulator The Universal Turing Machine Given: TM M & its input w Aim: Build another TM called H , that will output: accept if M accepts w, and reject otherwise An algorithm for H: Simulate M on w Implies: H is in RE accept, if M accepts w H(<M,w>) = reject, if M does does not accept w Question: If M does not halt on w, what will happen to H? 15
A Claim Claim: No H that is always guaranteed to halt, can exist! Proof: (Alan Turing, 1936) By contradiction, let us assume H exists accept <M,w> H reject 16
Therefore, if H exists D also should exist. But can such a D exist? (if not, then H also cannot exist) HP Proof (step 1) Let us construct a new TM D using H as a subroutine: On input <M>: Run H on input <M, <M> >; //(i.e., run M on M itself) Output the opposite of what H outputs; 1. 2. D accept accept <M> H <M, <M> > reject reject 17
HP Proof (step 2) The notion of inputing <M> to M itself A program can be input to itself (e.g., a compiler is a program that takes any program as input) accept, if M does not accept <M> D (<M>) = reject, if M accepts <M> Now, what happens if D is input to itself? accept, if D does not accept <D> D (<D>) = reject, if D accepts <D> A contradiction!!! ==> Neither D nor H can exist. 18
Of Paradoxes & Strange Loops E.g., Barber s paradox, Achilles & the Tortoise (Zeno s paradox) MC Escher s paintings A fun book for further reading: Godel, Escher, Bach: An Eternal Golden Braid by Douglas Hofstadter (Pulitzer winner, 1980) 19
The Diagonalization Language Example of a language that is not recursive enumerable (i.e, no TMs exist) 20
The Diagonalization language The Halting Problem Non-RE Languages x x Enumerable (RE) Recursively Context- Regular (DFA) sensitive Context Recursive free (PDA) 21
A Language about TMs & acceptance Let L be the language of all strings <M,w> s.t.: M is a TM (coded in binary) with input alphabet also binary w is a binary string M accepts input w. 1. 2. 3. 22
Enumerating all binary strings Let w be a binary string Then 1w i, where i is some integer E.g., If w= , then i=1; If w=0, then i=2; If w=1, then i=3; so on If 1w i, then call w as the ith word or ith binary string, denoted by wi. ==> A canonical ordering of all binary strings: { , 0, 1, 00, 01, 10, 11, 000, 100, 101, 110, ..} {w1, w2, w3, w4, . wi, } 23
Any TM M can also be binary- coded M = { Q, {0,1}, , , q0,B,F } Map all states, tape symbols and transitions to integers (==>binary strings) (qi,Xj) = (qk,Xl,Dm) will be represented as: ==> 0i1 0j1 0k1 0l1 0m Result: Each TM can be written down as a long binary string ==> Canonical ordering of TMs: {M1, M2, M3, M4, . Mi, } 24
The Diagonalization Language Ld = { wi | wi L(Mi) } The language of all strings whose corresponding machine does not accept itself (i.e., its own code) (input word w) j 1 0 1 0 1 2 1 1 1 0 3 0 0 0 0 4 1 0 1 1 ... Table: T[i,j] = 1, if Mi accepts wj = 0, otherwise. (TMs) 1 2 3 4 i Make a new language called Ld = {wi | T[i,i] = 0} 25 diagonal
Ld is not RE (i.e., has no TM) Proof (by contradiction): Let M be the TM for Ld ==> M has to be equal to some Mk s.t. L(Mk) = Ld ==> Will wk belong to L(Mk) or not? If wk L(Mk) ==> T[k,k]=1 ==> wk Ld If wk L(Mk) ==> T[k,k]=0 ==> wk Ld A contradiction either way!! 1. 2. 26
Why should there be languages that do not have TMs? We thought TMs can solve everything!! 27
Non-RE languages How come there are languages here? (e.g., diagonalization language) Non-RE Languages Enumerable (RE) Recursively Context- Regular (DFA) sensitive Context Recursive free (PDA) 28
One Explanation There are more languages than TMs By pigeon hole principle: ==> some languages cannot have TMs But how do we show this? Need a way to count & compare two infinite sets (languages and TMs) 29
How to count elements in a set? Let A be a set: If A is finite ==> counting is trivial If A is infinite ==> how do we count? And, how do we compare two infinite sets by their size? 30
Cantors definition of set size for infinite sets (1873 A.D.) Let N = {1,2,3, } Let E = {2,4,6, } (all natural numbers) (all even numbers) Q) Which is bigger? A) Both sets are of the same size Countably infinite Proof: Show by one-to-one, onto set correspondence from N ==> E n 1 2 3 . . f(n) 2 4 6 . . i.e, for every element in N, there is a unique element in E, and vice versa. 31
Example #2 Let Q be the set of all rational numbers Q = { m/n | for all m,n N } Claim: Q is also countably infinite; => |Q|=|N| 1/4 1/5 . 1/2 1/3 1/1 . 2/4 2/5 2/2 2/3 2/1 . 3/4 3/5 3/2 3/3 3/1 . 4/4 4/5 4/2 4/3 4/1 5/2 . 5/1 32
Really, really big sets! (even bigger than countably infinite sets) Uncountable sets Example: Let R be the set of all real numbers Claim: R is uncountable n 1 2 3 4 . . . f(n) Build x s.t. x cannot possibly occur in the table 3 . 1 4 1 5 9 5 . 5 5 5 5 5 0 . 1 2 3 4 5 0 . 5 1 4 3 0 E.g. x = 0 . 2 6 4 4 33
Therefore, some languages cannot have TMs The set of all TMs is countably infinite The set of all Languages is uncountable ==> There should be some languages without TMs ( by PHP) 34
Summary Problems vs. languages Decidability Recursive Undecidability Recursively Enumerable Not RE Examples of languages The diagonalization technique Reducability 41
