Computational Problems in Theory of Computation
CSE 105
THEORY OF COMPUTATION
Winter 2022
https://cseweb.ucsd.edu/classes/wi22/cse105-a/
Today's learning goals
Sipser Ch 4.1, 4.2
•
Trace high-level descriptions of algorithms for
computational problems.
•
Use counting arguments to prove the existence of
unrecognizable (undecidable) languages.
•
Use diagonalization in a proof of undecidability.
Encoding input for TMs
Sipser p. 159
•
B
y
d
e
f
i
n
i
t
i
o
n
,
T
M
i
n
p
u
t
s
a
r
e
s
t
r
i
n
g
s
•
To define TM M:
"On input w …
1.
..
2.
..
3.
…
For inputs that aren't strings,
w
e
h
a
v
e
t
o
e
n
c
o
d
e
t
h
e
o
b
j
e
c
t
(represent it as a string) first
N
o
t
a
t
i
o
n
:
<
O
>
i
s
t
h
e
s
t
r
i
n
g
t
h
a
t
r
e
p
r
e
s
e
n
t
s
(
e
n
c
o
d
e
s
)
t
h
e
o
b
j
e
c
t
O
<O
1
, …, O
n
> is the
single
string that
represents the tuple of objects O
1
, …, O
n
Encoding inputs
P
a
y
o
f
f
:
p
r
o
b
l
e
m
s
w
e
c
a
r
e
a
b
o
u
t
c
a
n
b
e
r
e
f
r
a
m
e
d
a
s
l
a
n
g
u
a
g
e
s
o
f
s
t
r
i
n
g
s
e.g. "Recognize whether a string is a palindrome."
{ w | w in {0,1}* and w = wR
}
e.g. "Check whether a string is accepted by a DFA."
{ <B,w> | B is a DFA over Σ, w in Σ*, and w is in L(B) }e.g. "Check whether the language of a PDA is infinite."
{ <A> | A is a PDA and L(A) is infinite}Encoding inputs
P
a
y
o
f
f
:
p
r
o
b
l
e
m
s
w
e
c
a
r
e
a
b
o
u
t
c
a
n
b
e
r
e
f
r
a
m
e
d
a
s
l
a
n
g
u
a
g
e
s
o
f
s
t
r
i
n
g
s
e.g. "Recognize whether a string is a palindrome."
{ w | w in {0,1}* and w = wR
}
A.
This set is regular and decidable.
B.
This set is regular and not decidable
C.
This set is nonregular and decidable
D.
This set is nonregular and not decidable.
E.
None of the above
Computational problems
A
c
o
m
p
u
t
a
t
i
o
n
a
l
p
r
o
b
l
e
m
i
s
d
e
c
i
d
a
b
l
e
i
f
f
t
h
e
l
a
n
g
u
a
g
e
e
n
c
o
d
i
n
g
t
h
e
p
r
o
b
l
e
m
i
n
s
t
a
n
c
e
s
i
s
d
e
c
i
d
a
b
l
e
Computational problems
Sample computational problems and their encodings:
•
A
D
F
A
"
C
h
e
c
k
w
h
e
t
h
e
r
a
s
t
r
i
n
g
i
s
a
c
c
e
p
t
e
d
b
y
a
D
F
A
.
"
{ <B,w> | B is a DFA over Σ, w in Σ*, and w is in L(B) }•
E
D
F
A
"
C
h
e
c
k
w
h
e
t
h
e
r
t
h
e
l
a
n
g
u
a
g
e
o
f
a
D
F
A
i
s
e
m
p
t
y
.
"
{ <A> | A is a DFA over Σ, L(A) is empty }•
E
Q
D
F
A
"
C
h
e
c
k
w
h
e
t
h
e
r
t
h
e
l
a
n
g
u
a
g
e
s
o
f
t
w
o
D
F
A
s
a
r
e
e
q
u
a
l
.
"
{ <A, B> | A and B are DFA over Σ, L(A) = L(B)}F
A
C
T
:
a
l
l
o
f
t
h
e
s
e
p
r
o
b
l
e
m
s
a
r
e
d
e
c
i
d
a
b
l
e
!
Computational problems
Sample computational problems and their encodings:
•
A
P
D
A
"
C
h
e
c
k
w
h
e
t
h
e
r
a
s
t
r
i
n
g
i
s
a
c
c
e
p
t
e
d
b
y
a
P
D
A
.
"
{ <B,w> | B is a PDA over Σ, w in Σ*, and w is in L(B) }•
E
P
D
A
"
C
h
e
c
k
w
h
e
t
h
e
r
t
h
e
l
a
n
g
u
a
g
e
o
f
a
P
D
A
i
s
e
m
p
t
y
.
"
{ <A> | A is a PDA over Σ, L(A) is empty }•
E
Q
P
D
A
"
C
h
e
c
k
w
h
e
t
h
e
r
t
h
e
l
a
n
g
u
a
g
e
s
o
f
t
w
o
P
D
A
s
a
r
e
e
q
u
a
l
.
"
{ <A, B> | A and B are PDA over Σ, L(A) = L(B)}F
A
C
T
:
s
o
m
e
o
f
t
h
e
s
e
p
r
o
b
l
e
m
s
a
r
e
d
e
c
i
d
a
b
l
e
,
a
n
d
s
o
m
e
a
r
e
n
o
t
!
Computational problems
Sample computational problems and their encodings:
•
A
T
M
"
C
h
e
c
k
w
h
e
t
h
e
r
a
s
t
r
i
n
g
i
s
a
c
c
e
p
t
e
d
b
y
a
T
M
.
"
{ <B,w> | B is a TM over Σ, w in Σ*, and w is in L(B) }•
E
T
M
"
C
h
e
c
k
w
h
e
t
h
e
r
t
h
e
l
a
n
g
u
a
g
e
o
f
a
T
M
i
s
e
m
p
t
y
.
"
{ <A> | A is a TM over Σ, L(A) is empty }•
E
Q
T
M
"
C
h
e
c
k
w
h
e
t
h
e
r
t
h
e
l
a
n
g
u
a
g
e
s
o
f
t
w
o
T
M
s
a
r
e
e
q
u
a
l
.
"
{ <A, B> | A and B are TM over Σ, L(A) = L(B)}F
A
C
T
:
a
l
l
o
f
t
h
e
s
e
p
r
o
b
l
e
m
s
a
r
e
u
n
d
e
c
i
d
a
b
l
e
!
Undecidable?
•
T
h
e
r
e
a
r
e
m
a
n
y
w
a
y
s
t
o
p
r
o
v
e
t
h
a
t
a
p
r
o
b
l
e
m
i
s
d
e
c
i
d
a
b
l
e
.
•
H
o
w
d
o
w
e
f
i
n
d
(
a
n
d
p
r
o
v
e
)
t
h
a
t
a
p
r
o
b
l
e
m
i
s
n
o
t
d
e
c
i
d
a
b
l
e
?
Before we proved the Pumping Lemma …
We proved there was a set that was not regular because
All sets of strings
Counting arguments
A
l
l
R
e
g
u
l
a
r
S
e
t
s
C
o
u
n
t
a
b
l
e
U
n
c
o
u
n
t
a
b
l
e
W
h
y
i
s
t
h
e
s
e
t
o
f
T
u
r
i
n
g
-
r
e
c
o
g
n
i
z
a
b
l
e
l
a
n
g
u
a
g
e
s
c
o
u
n
t
a
b
l
e
?
A.
It's equal to the set of all TMs, which we showed is countable.
B.
It's a subset of the set of all TMs, which we showed is countable.
C.
Each Turing-recognizable language is associated with a TM, so there
can be no more Turing-recognizable languages than TMs.
D.
More than one of the above.
E.
I don't know.
All sets of strings
Counting arguments
A
l
l
T
u
r
i
n
g
-
r
e
c
o
g
n
i
z
a
b
l
e
s
e
t
s
C
o
u
n
t
a
b
l
e
U
n
c
o
u
n
t
a
b
l
e
Satisfied?
•
Maybe not …
•
What's a specific example of a language that is not
Turing-recognizable? or not Turing-decidable?
•
Idea: consider a set that, were it to be Turing-decidable,
would have to "talk" about itself, and contradict itself!
A
TM
Recall A
DFA
= {<B,w> | B is a DFA and w is in L(B) }Decider for this set simulates arbitrary DFA
A
TM
= {<M,w> | M is a TM and w is in L(M) }Decider for this set simulates arbitrary TMs ???
A
TM
A
TM
= {<M,w> | M is a TM and w is in L(M) }Define the TM N = "On input <M,w>:
1.
Simulate M on w.
2.
If M accepts, accept. If M rejects, reject."
A
TM
A
TM
= {<M,w> | M is a TM and w is in L(M) }Define the TM N = "On input <M,w>:
1.
Simulate M on w.
2.
If M accepts, accept. If M rejects, reject."
W
h
a
t
i
s
L
(
N
)
?
A
TM
A
TM
= {<M,w> | M is a TM and w is in L(M) }Define the TM N = "On input <M,w>:
1.
Simulate M on w.
2.
If M accepts, accept. If M rejects, reject."
D
o
e
s
N
d
e
c
i
d
e
A
T
M
?
A
TM
A
TM
= {<M,w> | M is a TM and w is in L(M) }Define the TM N = "On input <M,w>:
1.
Simulate M on w.
2.
If M accepts, accept. If M rejects, reject."
C
o
n
c
l
u
d
e
:
A
T
M
i
s
T
u
r
i
n
g
-
r
e
c
o
g
n
i
z
a
b
l
e
.
I
s
i
t
d
e
c
i
d
a
b
l
e
?
Diagonalization proof: A
TM
not decidable
Sipser 4.11
Assume,
towards a contradiction
, that it is.
C
a
l
l
M
A
T
M
t
h
e
d
e
c
i
d
e
r
f
o
r
A
T
M
:
For every TM M and every string w,
•
Computation of M
ATM
on <M,w> halts and accepts if w is in L(M).
•
Computation of M
ATM
on <M,w> halts and rejects if w is not in L(M).
M
A
T
M
≠
N
Diagonalization proof: A
TM
not decidable
Sipser 4.11
Assume, towards a contradiction, that M
ATM
decides A
TM
Define the TM D = "On input <M>:
1.
Run M
ATM
on <M, <M>>.
2.
If M
ATM
accepts, reject; if M
ATM
rejects, accept."
Diagonalization proof: A
TM
not decidable
Sipser 4.11
Assume, towards a contradiction, that M
ATM
decides A
TM
Define the TM D = "On input <M>:
1.
Run M
ATM
on <M, <M>>.
2.
If M
ATM
accepts, reject; if M
ATM
rejects, accept."
Which of the following computations halt?
A.
Computation of D on <X>
B.
Computation of D on <Y> where Y is TM with L(Y) =Σ*
C.
Computation of D on <D>
D.
All of the above.
Diagonalization proof: A
TM
not decidable
Sipser 4.11
Assume, towards a contradiction, that M
ATM
decides A
TM
Define the TM D = "On input <M>:
1.
Run M
ATM
on <M, <M>>.
2.
If M
ATM
accepts, reject; if M
ATM
rejects, accept."
C
o
n
s
i
d
e
r
r
u
n
n
i
n
g
D
o
n
i
n
p
u
t
<
D
>
.
B
e
c
a
u
s
e
D
i
s
a
d
e
c
i
d
e
r
:
e
i
t
h
e
r
c
o
m
p
u
t
a
t
i
o
n
h
a
l
t
s
a
n
d
a
c
c
e
p
t
s
…
o
r
c
o
m
p
u
t
a
t
i
o
n
h
a
l
t
s
a
n
d
r
e
j
e
c
t
s
…
Diagonalization proof: A
TM
not decidable
Sipser 4.11
Assume, towards a contradiction, that M
ATM
decides A
TM
Define the TM D = "On input <M>:
1.
Run M
ATM
on <M, <M>>.
2.
If M
ATM
accepts, reject; if M
ATM
rejects, accept."
C
o
n
s
i
d
e
r
r
u
n
n
i
n
g
D
o
n
i
n
p
u
t
<
D
>
.
B
e
c
a
u
s
e
D
i
s
a
d
e
c
i
d
e
r
:
e
i
t
h
e
r
c
o
m
p
u
t
a
t
i
o
n
h
a
l
t
s
a
n
d
a
c
c
e
p
t
s
…
o
r
c
o
m
p
u
t
a
t
i
o
n
h
a
l
t
s
a
n
d
r
e
j
e
c
t
s
…
D
i
a
g
o
n
a
l
i
z
a
t
i
o
n
?
?
?
S
e
l
f
-
r
e
f
e
r
e
n
c
e
"
I
s
<
D
>
a
n
e
l
e
m
e
n
t
o
f
L
(
D
)
?
"
A
TM
•
Recognizable
•
Not decidable
F
a
c
t
:
A
l
a
n
g
u
a
g
e
i
s
d
e
c
i
d
a
b
l
e
i
f
f
i
t
a
n
d
i
t
s
c
o
m
p
l
e
m
e
n
t
a
r
e
b
o
t
h
r
e
c
g
o
n
i
z
a
b
l
e
.
C
o
r
o
l
l
a
r
y
:
T
h
e
c
o
m
p
l
e
m
e
n
t
o
f
A
T
M
i
s
u
n
r
e
c
o
g
n
i
z
a
b
l
e
.
Decidable vs. undecidable
W
h
i
c
h
o
f
t
h
e
f
o
l
l
o
w
i
n
g
l
a
n
g
u
a
g
e
s
i
s
u
n
d
e
c
i
d
a
b
l
e
?
A.
INFINITE
DFA
= { <A> | A is a DFA and L(A) is an infinite language}B.
S
TM
= { <M> | M is a TM and M has exactly 7 states}C.
Rev
DFA
= { <B> | B is a DFA and for all strings w, B accepts w iff itaccepts w
R
}
D.
Rec
TM
= { <X> | X is a TM and L(X) is recognizable}E.
Dec
TM
= { <Y> | Y is a TM and L(Y) is decidable}So far
Do we have to diagonalize?
•
Next time: comparing difficulty of problems.
Today's learning goals in the Theory of Computation class include understanding high-level algorithm descriptions, proving the existence of undecidable languages using counting arguments and diagonalization, and encoding inputs for Turing Machines. Computational problems can be reframed as languages of strings, leading to certain problems being decidable or undecidable based on the encodings used.
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.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
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.
E N D
Presentation Transcript
CSE 105 THEORY OF COMPUTATION Winter 2022 https://cseweb.ucsd.edu/classes/wi22/cse105-a/
Today's learning goals Sipser Ch 4.1, 4.2 Trace high-level descriptions of algorithms for computational problems. Use counting arguments to prove the existence of unrecognizable (undecidable) languages. Use diagonalization in a proof of undecidability.
Encoding input for TMs Sipser p. 159 By definition, TM inputs are strings For inputs that aren't strings, we have to encode the object (represent it as a string) first To define TM M: "On input w 1. .. 2. .. 3. Notation: <O> is the string that represents (encodes) the object O <O1, , On> is the single string that represents the tuple of objects O1, , On
Encoding inputs Payoff: problems we care about can be reframed as languages of strings e.g. "Recognize whether a string is a palindrome." { w | w in {0,1}* and w = wR } e.g. "Check whether a string is accepted by a DFA." { <B,w> | B is a DFA over , w in *, and w is in L(B) } e.g. "Check whether the language of a PDA is infinite." { <A> | A is a PDA and L(A) is infinite}
Encoding inputs Payoff: problems we care about can be reframed as languages of strings e.g. "Recognize whether a string is a palindrome." { w | w in {0,1}* and w = wR } A. This set is regular and decidable. B. This set is regular and not decidable C. This set is nonregular and decidable D. This set is nonregular and not decidable. E. None of the above
Computational problems A computational problem is decidable iff the language encoding the problem instances is decidable
Computational problems Sample computational problems and their encodings: ADFA "Check whether a string is accepted by a DFA." { <B,w> | B is a DFA over , w in *, and w is in L(B) } EDFA "Check whether the language of a DFA is empty." { <A> | A is a DFA over , L(A) is empty } EQDFA "Check whether the languages of two DFAs are equal." { <A, B> | A and B are DFA over , L(A) = L(B)} FACT: all of these problems are decidable!
Computational problems Sample computational problems and their encodings: APDA "Check whether a string is accepted by a PDA." { <B,w> | B is a PDA over , w in *, and w is in L(B) } EPDA "Check whether the language of a PDA is empty." { <A> | A is a PDA over , L(A) is empty } EQPDA "Check whether the languages of two PDAs are equal." { <A, B> | A and B are PDA over , L(A) = L(B)} FACT: some of these problems are decidable, and some are not!
Computational problems Sample computational problems and their encodings: ATM "Check whether a string is accepted by a TM." { <B,w> | B is a TM over , w in *, and w is in L(B) } ETM "Check whether the language of a TM is empty." { <A> | A is a TM over , L(A) is empty } EQTM "Check whether the languages of two TMs are equal." { <A, B> | A and B are TM over , L(A) = L(B)} FACT: all of these problems are undecidable!
Undecidable? There are many ways to prove that a problem is decidable. How do we find (and prove) that a problem is not decidable?
Counting arguments Before we proved the Pumping Lemma We proved there was a set that was not regular because Uncountable All Regular Sets All sets of strings Countable
Counting arguments Uncountable All Turing- recognizable sets Countable All sets of strings Why is the set of Turing-recognizable languages countable? A. It's equal to the set of all TMs, which we showed is countable. B. It's a subset of the set of all TMs, which we showed is countable. C. Each Turing-recognizable language is associated with a TM, so there can be no more Turing-recognizable languages than TMs. D. More than one of the above. E. I don't know.
Satisfied? Maybe not What's a specific example of a language that is not Turing-recognizable? or not Turing-decidable? Idea: consider a set that, were it to be Turing-decidable, would have to "talk" about itself, and contradict itself!
ATM Recall ADFA = {<B,w> | B is a DFA and w is in L(B) } Decider for this set simulates arbitrary DFA ATM = {<M,w> | M is a TM and w is in L(M) } Decider for this set simulates arbitrary TMs ???
ATM ATM = {<M,w> | M is a TM and w is in L(M) } Define the TM N = "On input <M,w>: 1. Simulate M on w. 2. If M accepts, accept. If M rejects, reject."
ATM ATM = {<M,w> | M is a TM and w is in L(M) } Define the TM N = "On input <M,w>: 1. Simulate M on w. 2. If M accepts, accept. If M rejects, reject." What is L(N)?
ATM ATM = {<M,w> | M is a TM and w is in L(M) } Define the TM N = "On input <M,w>: 1. Simulate M on w. 2. If M accepts, accept. If M rejects, reject." Does N decide ATM?
ATM ATM = {<M,w> | M is a TM and w is in L(M) } Define the TM N = "On input <M,w>: 1. Simulate M on w. 2. If M accepts, accept. If M rejects, reject." Conclude: ATM is Turing-recognizable. Is it decidable?
Diagonalization proof: ATM not decidable Sipser 4.11 Assume, towards a contradiction, that it is. Call MATM the decider for ATM: MATM N For every TM M and every string w, Computation of MATM on <M,w> halts and accepts if w is in L(M). Computation of MATM on <M,w> halts and rejects if w is not in L(M).
Diagonalization proof: ATM not decidable Sipser 4.11 Assume, towards a contradiction, that MATM decides ATM Define the TM D = "On input <M>: 1. Run MATM on <M, <M>>. 2. If MATM accepts, reject; if MATM rejects, accept."
Diagonalization proof: ATM not decidable Sipser 4.11 Assume, towards a contradiction, that MATM decides ATM Define the TM D = "On input <M>: 1. Run MATM on <M, <M>>. 2. If MATM accepts, reject; if MATM rejects, accept." Which of the following computations halt? A. Computation of D on <X> B. Computation of D on <Y> where Y is TM with L(Y) = * C. Computation of D on <D> D. All of the above.
Diagonalization proof: ATM not decidable Sipser 4.11 Assume, towards a contradiction, that MATM decides ATM Define the TM D = "On input <M>: 1. Run MATM on <M, <M>>. 2. If MATM accepts, reject; if MATM rejects, accept." Consider running D on input <D>. Because D is a decider: either computation halts and accepts or computation halts and rejects
Diagonalization proof: ATM not decidable Sipser 4.11 Assume, towards a contradiction, that MATM decides ATM Diagonalization??? Define the TM D = "On input <M>: 1. Run MATM on <M, <M>>. 2. If MATM accepts, reject; if MATM rejects, accept." "Is <D> an element of L(D)?" Self-reference Consider running D on input <D>. Because D is a decider: either computation halts and accepts or computation halts and rejects
ATM Recognizable Not decidable Fact: A language is decidable iff it and its complement are both recgonizable. Corollary: The complement of ATM is unrecognizable.
Decidable vs. undecidable Which of the following languages is undecidable? A. INFINITEDFA = { <A> | A is a DFA and L(A) is an infinite language} STM = { <M> | M is a TM and M has exactly 7 states} B. RevDFA = { <B> | B is a DFA and for all strings w, B accepts w iff it accepts wR} RecTM = { <X> | X is a TM and L(X) is recognizable} DecTM = { <Y> | Y is a TM and L(Y) is decidable} C. D. E.
So far Decidable Recognizable (and not decidable) ATM Co-recognizable (and not decidable) ATMC ADFA EDFA EQDFA INFINITEDFA RevDFA STM RecTM
Do we have to diagonalize? Next time: comparing difficulty of problems.
