Decidable Languages
Fall 2006
Costas Busch - RPI
1
Recall that:
A language L is Turing-Acceptable
if there is a Turing machine M
that accepts L
Also known as: Turing-Recognizable
or
Recursively-enumerable
languages
Fall 2006
Costas Busch - RPI
2
For any string w :
w L
M halts in an accept state
w L
M halts in a non-accept state
or loops forever
Fall 2006
Costas Busch - RPI
3
Definition:
A language L is decidable
if there is a Turing machine (decider) M
which accepts L
and halts on every input string
Also known as recursive languages
Fall 2006
Costas Busch - RPI
4
For any string w :
w L
M halts in an accept state
w L
M halts in a non-accept state
Every decidable language is Turing-Acceptable
Fall 2006
Costas Busch - RPI
5
Sometimes, it is convenient to have Turing
machines with single accept and reject states
q accept
q reject
These are the only halting states
That result to possible
halting configurations
Fall 2006
Costas Busch - RPI
6
We can convert any Turing machine to
have single accept and reject states
New machine
Old machine
q accept
x  x ,R
x  x ,R
x  x ,L
x  x ,R
Multiple
accept states
Fall 2006
For each tape symbol
x
One accept state
Costas Busch - RPI
7
Do the following for each possible
halting state:
New machine
Old machine
qi x  x , R
For each
qi
Multiple
reject states
Fall 2006
q reject
For all tape symbols x
not used for read in the
other transitions of q i
One reject state
Costas Busch - RPI
8
For a decidable language L :
Decider for L
q accept
Input
string
q reject
Decision
On Halt:
Accept
Reject
For each input string, the computation
halts in the accept or reject state
Fall 2006
Costas Busch - RPI
9
For a Turing-Acceptable language L :
Turing Machine for L
q accept
Input
string
q reject
It is possible that for some input string
the machine enters an infinite loop
Fall 2006
Costas Busch - RPI
10
Problem:
Is number x prime?
Corresponding language:
PRIMES
 {1, 2, 3, 5, 7,  }
We will show it is decidable
Fall 2006
Costas Busch - RPI
11
Decider for PRIMES :
On input number x :
Divide x with all possible numbers
between 2 and x
If any of them divides x
Then reject
Else accept
Fall 2006
Costas Busch - RPI
12
the decider for the language
solves the corresponding problem
Decider for PRIMES
q accept
Input number x
(Input string)
Fall 2006
YES
is x prime?
(Accept)
q reject
(Reject)
Costas Busch - RPI
NO
13
Theorem:
If a language L is decidable,
then its complement L is decidable too
Proof:
Build a Turing machine M  that
accepts L and halts on every input string
( M  is decider for L )
Fall 2006
Costas Busch - RPI
14
Transform accept state to reject
and vice-versa
M
M
q accept

q reject
qa
qa
q reject

q accept
qr
Fall 2006
qr
Costas Busch - RPI
15
Turing Machine M 
On each input string w do:
1. Let M be the decider for L
2. Run M with input string
If M
If M
w
accepts then reject
rejects then accept
Accepts L and halts on every input string
Fall 2006
Costas Busch - RPI
END OF PROOF
16
Undecidable Languages
An undecidable language has no decider:
each Turing machine that accepts L
does not halt on some input string
We will show that:
There is a language which is
Turing-Acceptable and undecidable
Fall 2006
Costas Busch - RPI
17
We will prove that there is a language
L:
•
is not Turing-acceptable
(not accepted by any Turing Machine)
•
L
L
is Turing-acceptable
the complement of a
decidable language is decidable
Therefore,
Fall 2006
L
is undecidable
Costas Busch - RPI
18
Non Turing-Acceptable
Turing-Acceptable
L
L
Decidable
Fall 2006
Costas Busch - RPI
19
A Language which
is not
Turing Acceptable
Fall 2006
Costas Busch - RPI
20
Consider alphabet
Strings of
{a }
{a } :

a , aa , aaa , aaaa , 
a
Fall 2006
1
a
2
a
3
Costas Busch - RPI
a
4

21
Consider Turing Machines
that accept languages over alphabet {a }
They are countable:
M 1, M 2 , M 3 , M 4 , 
(There is an enumerator that generates them)
Fall 2006
Costas Busch - RPI
22
Each machine accepts some language over {a }
M 1, M 2 , M 3 , M 4 , 
L ( M 1 ), L ( M 2 ), L ( M 3 ), L ( M 4 ), 
Note that it is possible to have
L(M i )  L(M j )
for
i j
Since, a language could be accepted by more than one
Turing machine
Fall 2006
Costas Busch - RPI
23
Example language accepted by M i
L ( M i )  { aa , aaaa , aaaaaa }
2
4
6
L ( M i )  {a , a , a }
Binary representation
a
L(M i )
Fall 2006
1
0
a
1
2
a
3
0
a
4
1
Costas Busch - RPI
a
5
0
a
1
6
a
7
0


24
Example of binary representations
a
1
a
2
a
3
a
4

L(M 1)
0
1
0
1

L(M 2 )
1
0
0
1

L(M 3 )
0
1
1
1

L(M 4 )
0
0
0
1

Fall 2006
Costas Busch - RPI
25
Consider the language
i
i
L  { a : a  L ( M i )}
L
Fall 2006
consists of the 1’s in the diagonal
Costas Busch - RPI
26
a
1
2
a
a
3
a
4

L(M 1)
0
1
0
1

L(M 2 )
1
0
0
1

L(M 3 )
0
1
1
1

L(M 4 )
0
0
0
1

3
4
L  { a , a , }
Fall 2006
Costas Busch - RPI
27
Consider the language
i
i
i
i
L
L  { a : a  L ( M i )}
L  { a : a  L ( M i )}
L
Fall 2006
consists of the 0’s in the diagonal
Costas Busch - RPI
28
a
1
a
2
a
3
a
4

L(M 1)
0
1
0
1

L(M 2 )
1
0
0
1

L(M 3 )
0
1
1
1

L(M 4 )
0
0
0
1

1
2
L  { a , a , }
Fall 2006
Costas Busch - RPI
29
Theorem:
Language L is not Turing-Acceptable
Proof:
Assume for contradiction that
L is Turing-Acceptable
There must exist some machine M k
that accepts L :
L(M k )  L
Fall 2006
Costas Busch - RPI
30
a
1
a
2
a
3
a
4

L(M 1)
0
1
0
1

L(M 2 )
1
0
0
1

L(M 3 )
0
1
1
1

L(M 4 )
0
0
0
1

Question: M k  M 1 ?
Fall 2006
Costas Busch - RPI
L(M k )  L
31
a
1
a
2
a
3
a
4

L(M 1)
0
1
0
1

L(M 2 )
1
0
0
1

L(M 3 )
0
1
1
1

L(M 4 )
0
0
0
1

1
Answer:
Fall 2006
a  L(M k )
M k  M1
1
Costas Busch - RPI
a  L(M 1)
32
a
1
a
2
a
3
a
4

L(M 1)
0
1
0
1

L(M 2 )
1
0
0
1

L(M 3 )
0
1
1
1

L(M 4 )
0
0
0
1

Question: M k  M 2 ?
Fall 2006
Costas Busch - RPI
L(M k )  L
33
a
1
a
2
a
3
a
4

L(M 1)
0
1
0
1

L(M 2 )
1
0
0
1

L(M 3 )
0
1
1
1

L(M 4 )
0
0
0
1

2
Answer:
Fall 2006
a  L(M k )
Mk  M2
2
Costas Busch - RPI
a  L(M 2 )
34
a
1
a
2
a
3
a
4

L(M 1)
0
1
0
1

L(M 2 )
1
0
0
1

L(M 3 )
0
1
1
1

L(M 4 )
0
0
0
1

Question: M k  M
Fall 2006
3 ?
Costas Busch - RPI
L(M k )  L
35
a
1
a
2
a
3
a
4

L(M 1)
0
1
0
1

L(M 2 )
1
0
0
1

L(M 3 )
0
1
1
1

L(M 4 )
0
0
0
1

3
Answer:
Fall 2006
a  L(M k )
Mk  M3
3
Costas Busch - RPI
a  L(M 3 )
36
Similarly:
Mk  Mi
for any
i
Because either:
i
a  L(M k )
i
or
i
a  L(M k )
i
a  L(M i )
a  L(M i )
the machine M k cannot exist
L is not Turing-Acceptable
Fall 2006
Costas Busch - RPI
End of Proof
37
Non Turing-Acceptable
L
Turing-Acceptable
Decidable
Fall 2006
Costas Busch - RPI
38
A Language which is
Turing-Acceptable
and Undecidable
Fall 2006
Costas Busch - RPI
39
We will prove that the language
i
i
L  { a : a  L ( M i )}
Is TuringAcceptable
There is a
Turing machine
that accepts L
Fall 2006
Undecidable
Each machine
that accepts L
doesn’t halt
on some input string
Costas Busch - RPI
40
a
1
2
a
a
3
a
4

L(M 1)
0
1
0
1

L(M 2 )
1
0
0
1

L(M 3 )
0
1
1
1

L(M 4 )
0
0
0
1

3
4
L  { a , a , }
Fall 2006
Costas Busch - RPI
41
Theorem:
The language
i
i
L  { a : a  L ( M i )}
Is Turing-Acceptable
Proof: We will give a Turing Machine that
accepts L
Fall 2006
Costas Busch - RPI
42
Turing Machine that accepts L
For any input string w
• Compute i , for which w  a
i
• Find Turing machine M i
(using the enumerator for Turing Machines)
• Simulate M i on input a
i
• If M i accepts, then accept w
End of Proof
Fall 2006
Costas Busch - RPI
43
Observation:
Turing-Acceptable
i
i
L  { a : a  L ( M i )}
Not Turing-acceptable
i
i
L  { a : a  L ( M i )}
(Thus, L
Fall 2006
is undecidable)
Costas Busch - RPI
44
Non Turing-Acceptable
Turing-Acceptable
L
L
Decidable
L?
Fall 2006
Costas Busch - RPI
45
Theorem:
Proof:
If
i
i
L  { a : a  L ( M i )}
is undecidable
L
is decidable
the complement of a
decidable language is decidable
Then L is decidable
However, L is not Turing-Acceptable!
Contradiction!!!!
Fall 2006
Costas Busch - RPI
46
Not Turing-Acceptable
Turing-Acceptable
L
L
Decidable
Fall 2006
Costas Busch - RPI
47
Turing acceptable languages
and
Enumerators
Fall 2006
Costas Busch - RPI
48
We will prove:
(weak result)
• If a language is decidable then
there is an enumerator for it
(strong result)
• A language is Turing-acceptable
if and only if
there is an enumerator for it
Fall 2006
Costas Busch - RPI
49
Theorem:
if a language L is decidable then
there is an enumerator for it
Proof:
Let M be the decider for L
Use M to build the enumerator for L
Fall 2006
Costas Busch - RPI
50
~
Let M be an enumerator that prints
all strings from input alphabet in proper order
Example:
alphabet is { a , b }
Fall 2006
a
b
aa
ab
ba (proper order)
bb
aaa
aab
......
Costas Busch - RPI
51
Enumerator for L
Repeat:
~
1. M
generates a string w
2. M
checks if w  L
YES: print w to output
NO:
ignore w
This part terminates,
because L is decidable
Fall 2006
Costas Busch - RPI
52
Enumerator for L
~
M
Give me
Enumerates all
strings of
input alphabet
next string
string w i
M
If M accepts w i
then print w i to
output
output
All strings
of
Generates all
Strings in alphabet
Fall 2006
L
Tests each string
if it is accepted by M
Costas Busch - RPI
53
Example: L  {b , ab , bb , aaa ,....}
~
M
w1
w2
w3
Fall 2006
a
b
aa
ab
ba
bb
aaa
aab
M
reject
accept
reject
accept
Enumeration
Output
b
ab
reject
accept
accept
bb
aaa
reject
Costas Busch - RPI
END OF PROOF
54
Theorem:
if language L is Turing-Acceptable then
there is an enumerator for it
Proof:
Let M be the Turing machine that accepts L
Use M to build the enumerator for L
Fall 2006
Costas Busch - RPI
55
Enumerator for L
~
M
M
Enumerates all
strings of input alphabet
in proper order
Fall 2006
Costas Busch - RPI
Accepts L
56
NAIVE APPROACH
Enumerator for L
~
Repeat:
M generates a string w
M
checks if w  L
YES: print w to output
NO:
ignore w
Problem: If w  L
machine M
Fall 2006
Costas Busch - RPI
may loop forever
57
BETTER APPROACH
~ Generates first string w
M
1
M
~
M
executes first step on w1
Generates second string w 2
M
executes first step on w 2
second step on w1
Fall 2006
Costas Busch - RPI
58
~
M
Generates third string
M
w3
executes first step on w 3
second step on w 2
third step on
w1
And so on............
Fall 2006
Costas Busch - RPI
59
String: w1
Step in
computation
of string
Fall 2006
w2
w3
1
1
1
1
2
2
2
2
3
3
3
3
4
4
4
4
Costas Busch - RPI
w 4 
60
If for any string w i
machine M halts in an accepting state
then print w i on the output
End of Proof
Fall 2006
Costas Busch - RPI
61
Theorem:
If for language L
there is an enumerator
then L is Turing-Acceptable
Proof:
Using the enumerator for L
we will build a Turing machine
that accepts L
Fall 2006
Costas Busch - RPI
62
Input Tape
w
Turing Machine that accepts L
Enumerator
for L
Fall 2006
w
wi
Give me the
next string
in the
enumeration
sequence
Compare
If same,
Accept and Halt
Costas Busch - RPI
63
Turing machine that accepts
L
For any input string w
Loop:
• Using the enumerator of L ,
generate the next string of L
• Compare generated string with w
If same, accept and exit loop
End of Proof
Fall 2006
Costas Busch - RPI
64
By combining the last two theorems,
we have proven:
A language is Turing-Acceptable
if and only if
there is an enumerator for it
Fall 2006
Costas Busch - RPI
65
Descargar

Languages and Finite Automata