Non-SD Languages in Theory of Computation
M
A
/
C
S
S
E
4
7
4
T
h
e
o
r
y
o
f
C
o
m
p
u
t
a
t
i
o
n
Non-SD Reductions
Your Questions?
•
Previous class days'
material
•
Reading Assignments
•
HW 15 problems
•
Anything else
Informal Poll:
How is your understanding of reductions and proving undecidability?
1 2 3 4 5 6
Totally Easy for
Lost me now!
{<
M
,
q
>
:
M
r
e
a
c
h
e
s
q
o
n
s
o
m
e
i
n
p
u
t
}
H
i
d
d
e
n
:
M
r
e
a
c
h
e
s
q
o
n
s
o
m
e
i
n
p
u
t
H
ANY
= {<M
> : there exists some string on which TM
M
halts}
R
(?
Oracle
)
L
2
= {<M
,
q
> :
M
reaches
q
on some input}
R
(<
M
>) =
1. Build <
M
#> so that
M
# is identical to
M
except that, if
M
has a transition
((
q
1
,
c
1
), (
q
2
,
c
2
,
d
)) and
q
2
is a halting state other than
h
, replace that
transition with:
((
q
1
,
c
1
), (
h
,
c
2
,
d
)).
2. Return <
M
#,
h
>.
If
Oracle
exists, then
C
=
Oracle
(
R
(<
M
>)) decides H
ANY
:
●
R
can be implemented as a Turing machine.
●
C
is correct:
M
# will reach the halting state
h
iff
M
would reach some
halting state. So:
● <
M
>
H
ANY
: There is some string on which
M
halts. So there is some
string on which
M
# reaches state
h
.
Oracle
accepts.
● <
M
>
H
ANY
: There is no string on which
M
halts. So there is no string
on which
M
# reaches state
h
.
Oracle
rejects.
But no machine to decide H
ANY
can exist, so neither does
Oracle
.
Side Road with a purpose:
obtainSelf
From Section 25.3:
I
n
s
e
c
t
i
o
n
2
5
.
3
,
t
h
e
a
u
t
h
o
r
p
r
o
v
e
s
t
h
e
e
x
i
s
t
e
n
c
e
o
f
a
v
e
r
y
u
s
e
f
u
l
c
o
m
p
u
t
a
b
l
e
f
u
n
c
t
i
o
n
:
o
b
t
a
i
n
S
e
l
f
.
W
h
e
n
c
a
l
l
e
d
a
s
a
s
u
b
r
o
u
t
i
n
e
b
y
a
n
y
T
u
r
i
n
g
m
a
c
h
i
n
e
M
,
o
b
t
a
i
n
S
e
l
f
w
r
i
t
e
s
<
M
>
o
n
t
o
M
'
s
t
a
p
e
.
R
e
l
a
t
e
d
t
o
q
u
i
n
e
s
:
A
q
u
i
n
e
i
s
a
c
o
m
p
u
t
e
r
p
r
o
g
r
a
m
w
h
i
c
h
t
a
k
e
s
n
o
i
n
p
u
t
a
n
d
p
r
o
d
u
c
e
s
a
c
o
p
y
o
f
i
t
s
o
w
n
s
o
u
r
c
e
c
o
d
e
a
s
i
t
s
o
n
l
y
o
u
t
p
u
t
.
Definition is from
http://en.wikipedia.org/wiki/Quine_(computing)
Some quines
•
main(){char q=34, n=10,*a="main() {charq=34,n=10,*a=%c%s%c;
printf(a,q,a,q,n);}%c";printf(a,q,a,q,n);}
•
((lambda (x) (list x (list 'quote x)))
(quote (lambda (x) (list x (list 'quote x)))))
•
Quine's paradox and a related sentence:
"Yields falsehood when preceded by its quotation" yields
falsehood when preceded by its quotation.
"quoted and followed by itself is a quine." quoted and
followed by itself is a quine.
There is an uncountable number of non-SD languages, but only a
countably infinite number of TM’s (hence SD languages).
The class
of non-SD languages is
much
bigger than that of SD languages!
N
o
n
-
S
D
L
a
n
g
u
a
g
e
s
I
n
t
u
i
t
i
o
n
:
N
o
n
-
S
D
l
a
n
g
u
a
g
e
s
u
s
u
a
l
l
y
i
n
v
o
l
v
e
e
i
t
h
e
r
i
n
f
i
n
i
t
e
search (where testing each potential member could loop
forever), or determining whether a TM will infinite loop.
Examples:
•
H = {<M
,
w
> : TM
M
does
not
halt on
w
}.
•
{<M
> :
L
(
M
) =
*}.
•
{<M
> : TM
M
halts on nothing}.
N
o
n
-
S
D
L
a
n
g
u
a
g
e
s
● Contradiction
●
L
is the complement of an SD/D Language.
● Reduction from a known non-SD language
P
r
o
v
i
n
g
L
a
n
g
u
a
g
e
s
a
r
e
n
o
t
S
D
T
h
e
o
r
e
m
:
T
M
M
I
N
=
{<M
>: Turing machine
M
is minimal} is not in SD.
By "minimal", we mean that <M> is minimal among all encodings of
TMs that are equivalent to M.
C
o
n
t
r
a
d
i
c
t
i
o
n
E
x
a
m
p
l
e
T
h
e
o
r
e
m
:
T
M
M
I
N
=
{<M
>: Turing machine
M
is minimal} is not in SD.
P
r
o
o
f
:
I
f
T
M
M
I
N
w
e
r
e
i
n
S
D
,
t
h
e
n
t
h
e
r
e
w
o
u
l
d
e
x
i
s
t
s
o
m
e
T
u
r
i
n
g
machine
ENUM
that enumerates its elements. Define the following
Turing machine:
M#
(
x
) =
1. Invoke
obtainSelf
to produce <
M#
>.
2. Run
ENUM
until it generates the description of some Turing
machine
M
whose description is longer than |<
M#
>|.
3. Invoke
U
on the string <
M
,
x
>.
Since TM
MIN
is infinite,
ENUM
must eventually generate a string that
is longer than |<
M#
>|. So
M#
makes it to step 3 and thus M# is
Equivalent to
M
since it simulates
M
. But, since |<
M#
>| < |<
M
>|,
M
cannot be minimal.
But M#'s description was generated by
ENUM
. Contradiction.
H
i
d
d
e
n
:
C
o
n
t
r
a
d
i
c
t
i
o
n
Suppose we want to know whether
L
is in SD and we know:
●
L
is in SD, and
●
At least one of
L
or
L
is not in D.
Then we can conclude that
L
is not in SD, because, if it were,
it would force both itself and its complement into D, which we
know cannot be true.
Example:
●
H (since
(
H) = H is in SD and not in D)
T
h
e
C
o
m
p
l
e
m
e
n
t
o
f
L
i
s
i
n
S
D
/
D
A
anbn
contains strings that look like:
(
q00,a00,q01,a00,
),
(
q00,a01,q00,a10,
),
(
q00,a10,q01,a01,
),
(
q00,a11,q01,a10,
),
(
q01,a00,q00,a01,
),
(
q01,a01,q01,a10,
),
(
q01,a10,q01,a11,
),
(
q01,a11,q11,a01,
)
It does not contain strings like
aaabbb
.
But A
n
B
n
does.
A
a
n
b
n
=
{<
M
>
:
L
(
M
)
=
A
n
B
n
}
T
r
y
t
h
i
s
o
n
e
:
H = {<M
,
w
> : TM
M
does not halt on
w
}
R
(?
Oracle
)
A
anbn
= {<M
> :
L
(
M
) = A
n
B
n
}
R
(<
M
,
w
>) =
1. Construct the description <
M
#>, where
M
#(
x
) operates as follows:
1.1. Erase the tape.
1.2. Write
w
on the tape.
1.3. Run
M
on
w
.
1.4. Accept.
2. Return <
M
#>.
If
Oracle
exists,
C
=
Oracle
(
R
(<
M
,
w
>)) semidecides
H:
A
a
n
b
n
=
{<
M
>
:
L
(
M
)
=
A
n
B
n
}
A
l
s
o
t
r
y
:
H
=
{<
M
,
w
>
:
T
M
M
d
o
e
s
n
o
t
h
a
l
t
o
n
w
}
R
(?
Oracle
)
A
anbn
= {<M
> :
L
(
M
) = A
n
B
n
}
R
(<
M
,
w
>) =
1. Construct the description <
M
#>, where
M
#(
x
) operates as
follows:
1.1 Copy the input
x
to another track for later.
1.2. Erase the tape.
1.3. Write
w
on the tape.
1.4. Run
M
on
w
.
1.5. Put
x
back on the tape.
1.6. If
x
A
n
B
n
then accept, else loop.
2. Return <
M
#>.
If
Oracle
exists,
C
=
Oracle
(
R
(<
M
,
w
>)) semidecides
H:
A
a
n
b
n
=
{<
M
>
:
L
(
M
)
=
A
n
B
n
}
i
s
n
o
t
S
D
A
n
d
t
r
y
t
h
i
s
o
n
e
R
(
<
M
,
w
>
)
r
e
d
u
c
e
s
H
t
o
A
a
n
b
n
:
1. Construct the description <
M
#>:
1.1. If
x
A
n
B
n
then accept. Else:
1.2. Erase the tape.
1.3. Write
w
on the tape.
1.4. Run
M
on
w
.
1.5. Accept.
2. Return <
M
#>.
If
Oracle
exists, then
C
=
Oracle
(
R
(<
M
,
w
>)) semidecides
H:
A
a
n
b
n
=
{<
M
>
:
L
(
M
)
=
A
n
B
n
}
i
s
n
o
t
S
D
What about:
H = {<M
,
w
> : TM
M
does not halt on
w
}
R
(?
Oracle
)
H
ALL
= {<M
> : TM halts on
*}
R
e
d
u
c
t
i
o
n
A
t
t
e
m
p
t
1
:
R
(
<
M
,
w
>
)
=
1. Construct the description <
M
#>, where
M
#(
x
)
operates as follows:
1.1. Erase the tape.
1.2. Write
w
on the tape.
1.3. Run
M
on
w
.
2. Return <
M
#>.
H
A
L
L
=
{<
M
>
:
T
M
h
a
l
t
s
o
n
*
}
H = {<M
,
w
> : TM
M
does not halt on
w
}
R
(?
Oracle
)
H
ALL
= {<M
> : TM halts on
*}
R
e
d
u
c
t
i
o
n
A
t
t
e
m
p
t
1
:
R
(
<
M
,
w
>
)
=
1. Construct the description <
M
#>, where
M
#(
x
) operates as follows:
1.1. Erase the tape.
1.2. Write
w
on the tape.
1.3. Run
M
on
w
.
2. Return <
M
#>.
If
Oracle
exists,
C
=
Oracle
(
R
(<
M
,
w
>)) semidecides
H:
● <
M
,
w
>
H:
M
does not halt on
w
, so
M
# gets stuck in step 1.3
a
n
d
h
a
l
t
s
o
n
n
o
t
h
i
n
g
.
O
r
a
c
l
e
d
o
e
s
n
o
t
a
c
c
e
p
t
.
●
<
M
,
w
>
H
:
M
h
a
l
t
s
o
n
w
,
s
o
M
#
h
a
l
t
s
o
n
e
v
e
r
y
t
h
i
n
g
.
O
r
a
c
l
e
a
c
c
e
p
t
s
.
T
h
e
r
e
M
a
y
B
e
N
o
E
a
s
y
W
a
y
t
o
F
l
i
p
R
(<
M
,
w
>) reduces
H to H
ALL
:
1. Construct the description <
M
#>, where
M
#(
x
) operates as
follows:
1.1. Copy the input
x
to another track for later.
1.2. Erase the tape.
1.3. Write
w
on the tape.
1.4. Run
M
on
w
for |
x
| steps or until
M
naturally halts.
1.5. If
M
naturally halted, then loop.
1.6. Else halt.
2. Return <
M
#>.
If
Oracle
exists,
C
=
Oracle
(
R
(<
M
,
w
>)) semidecides
H:
● <
M
,
w
>
H: No matter how long
x
is,
M
will not halt in |
x
|
steps. So, for all inputs
x
,
M
# makes it to step 1.6. So it
h
a
l
t
s
o
n
e
v
e
r
y
t
h
i
n
g
.
O
r
a
c
l
e
a
c
c
e
p
t
s
.
● <
M
,
w
>
H:
M
halts on
w
in
n
steps. On inputs
of length less than
n
,
M
# makes it to step 1.6 and halts.
But on all inputs of length
n
or greater,
M
# will loop in step
1
.
5
.
O
r
a
c
l
e
d
o
e
s
n
o
t
a
c
c
e
p
t
.
H
A
L
L
=
{<
M
>
:
T
M
h
a
l
t
s
o
n
*
}
E
q
T
M
s
=
{<
M
a
,
M
b
>
:
L
(
M
a
)
=
L
(
M
b
)
}
We’ve already shown it’s not in D.
Now we show it’s also not in SD.
E
q
T
M
s
=
{<
M
a
,
M
b
>
:
L
(
M
a
)
=
L
(
M
b
)
}
H = {<M
,
w
> : TM
M
does not halt on
w
}
R
(?
Oracle
)
EqTMs = {<M
a
,
M
b
> :
L
(
M
a
) =
L
(
M
b
)}
R
(<
M
,
w
>) =
1. Construct the description <
M
#>:
2. Construct the description <
M
?>:
3. Return <
M
#,
M
?>.
If
Oracle
exists,
C
=
Oracle
(
R
(<
M
,
w
>)) semidecides
H:
● <
M
,
w
>
H:
● <
M
,
w
>
H:
E
q
T
M
s
=
{<
M
a
,
M
b
>
:
L
(
M
a
)
=
L
(
M
b
)
}
R
(<
M
,
w
>) =
1. Construct the description <
M
#>:
1.1 Erase the tape.
1.2 Write
w
on the tape.
1.3 Run
M
on
w
.
1.4 Accept.
2. Construct the description <
M
?>:
1.1 Loop.
3. Return <
M
#,
M
?>.
If
Oracle
exists,
C
=
Oracle
(
R
(<
M
,
w
>)) semidecides
H:
M
?
halts on nothing.
● <
M
,
w
>
H:
M
does not halt on
w
, so
M
# gets stuck
i
n
s
t
e
p
1
.
3
a
n
d
h
a
l
t
s
o
n
n
o
t
h
i
n
g
.
O
r
a
c
l
e
a
c
c
e
p
t
s
.
● <
M
,
w
>
H:
M
halts on
w
, so
M
# halts on
e
v
e
r
y
t
h
i
n
g
.
O
r
a
c
l
e
d
o
e
s
n
o
t
a
c
c
e
p
t
.
L
1
= {<M
>:
M
has an even number of states}.
L
2
= {<M
>: |<
M
>| is even}.
L
3
= {<M
>: |
L
(
M
)| is even}.
L
4
= {<M
>:
M
accepts all even length strings}.
T
h
e
D
e
t
a
i
l
s
M
a
t
t
e
r
L
1
= {<M
>:
M
has an even number of states}.
L
2
= {<M
>: |<
M
>| is even}.
L
3
= {<M
>: |
L
(
M
)| is even}.
H
M
L
3
:
R
(<
M
,
w
>) =
1. Construct the description <
M
#>, where
M
#(
x
) operates as follows:
1.1 Copy the input
x
to another track for later.
1.2 Erase the tape.
1.3 Write
w
on the tape.
1.4 Run
M
on
w
.
1.5 If x =
then accept. Else loop.
2. Return <
M
#>.
● <
M
,
w
>
H:
● <
M
,
w
>
H:
H
i
d
d
e
n
:
T
h
e
D
e
t
a
i
l
s
M
a
t
t
e
r
L
1
= {<M
>:
M
has an even number of states}.
L
2
= {<M
>: |<
M
>| is even}.
L
3
= {<M
>: |
L
(
M
)| is even}.
L
4
= {<M
>:
M
accepts all even length strings}.
T
h
e
D
e
t
a
i
l
s
M
a
t
t
e
r
L
1
= {<M
>:
M
has an even number of states}.
L
2
= {<M
>: |<
M
>| is even}.
L
3
= {<M
>: |
L
(
M
)| is even}.
L
4
= {<M
>:
M
accepts all even length strings}
T
h
e
D
e
t
a
i
l
s
M
a
t
t
e
r
H
M
L
4
:
R
(<
M
,
w
>) =
1. Construct the description <
M
#>, where
M
#(
x
) operates as follows:
1.1 Copy the input
x
to another track for later.
1.2 Erase the tape.
1.3 Write
w
on the tape.
1.4 Run
M
on
w
for |
x
| steps or until
M
naturally halts.
1.5 If
M
halted naturally, then
loop. Else accept.
2. Return <
M
#>.
● <
M
,
w
>
H:
● <
M
,
w
>
H:
Consider :
L
1
= {<M
,
w
>:
M
rejects
w
}.
L
2
= {<M
,
w
>:
M
does not halt on
w
}.
L
3
= {<M
,
w
>:
M
is a deciding TM and rejects
w
}.
A
c
c
e
p
t
i
n
g
,
R
e
j
e
c
t
i
n
g
,
H
a
l
t
i
n
g
,
a
n
d
L
o
o
p
i
n
g
{<
M
,
w
>
:
M
i
s
a
D
e
c
i
d
i
n
g
T
M
a
n
d
R
e
j
e
c
t
s
w
}
H = {<M
,
w
> : TM
M
does not halt on
w
}
R
(?
Oracle
)
{<M
,
w
>:
M
is a deciding TM and rejects
w
}
R
(<
M
,
w
>) =
1. Construct the description <
M
#>, where
M
#(
x
) operates as follows:
1.1 Erase the tape.
1.2 Write
w
on the tape.
1.3 Run
M
on
w
.
1.4 Reject.
2. Return <
M
#,
>.
If
Oracle
exists,
C
=
Oracle
(
R
(<
M
,
w
>)) semidecides
H:
● <
M
,
w
>
H:
● <
M
,
w
>
H:
Problem:
{<
M
,
w
>
:
M
i
s
a
D
e
c
i
d
i
n
g
T
M
a
n
d
R
e
j
e
c
t
s
w
}
H
ALL
= {<M
> : TM
M
halts on
*
}
R
(?
Oracle
)
{<M
,
w
>:
M
is a deciding TM and rejects
w
}
R
(<
M
>) =
1. Construct the description <
M
#>, where
M
#(
x
) operates as follows:
1.1 Run
M
on
x
.
1.2 Reject.
2. Return <
M
#,
>.
If
Oracle
exists,
C
=
Oracle
(
R
(<
M
>)) semidecides H
ALL
:
● <
M
>
H
ALL
:
M
# halts and rejects all inputs.
Oracle
accepts.
● <
M
>
H
ALL
: There is at least one input on which
M
doesn’t halt. So
M
#
is not a deciding TM.
Oracle
does not accept.
No machine to semidecide H
ALL
can exist, so neither does
Oracle
.
W
h
a
t
A
b
o
u
t
T
h
e
s
e
?
L
1
= {a
}.
L
2
= {<M
> :
M
accepts
a
}.
L
3
= {<M
> :
L
(
M
) = {a
}}.
H
i
d
d
e
n
:
W
h
a
t
A
b
o
u
t
T
h
e
s
e
?
L
1
= {a
}.
L
2
= {<M
> :
M
accepts
a
}.
L
3
= {<M
> :
L
(
M
) = {a
}}.
H
≤
L
3
:
R
(<
M
,
w
>) =
1. Construct the description <
M
#>, where
M
#(
x
) operates as follows:
1.1 If
x
=
a
, accept.
1.2 Erase the tape.
1.2 Write
w
on the tape.
1.3 Run
M
on
w
.
1.4 A
ccept.
2. Return <
M
#>.
● <
M
,
w
>
H:
● <
M
,
w
>
H:
{<
M
a
,
M
b
>
:
L
(
M
a
)
–
L
(
M
b
)
}
{<
M
a
,
M
b
>
:
L
(
M
a
)
–
L
(
M
b
)
}
R
( ) =
Return <
M
?,
M
#>.
<
M
,
w
>
H:
L
(
M
?) -
L
(
M
#) =
<
M
,
w
>
H:
L
(
M
?) -
L
(
M
#) =
{<
M
a
,
M
b
>
:
L
(
M
a
)
–
L
(
M
b
)
}
R
is a reduction from
H.
R
(<
M
,
w
>) =
1. Construct the description of
M
#(
x
) that operates as follows:
1.1. Erase the tape.
1.2. Write
w
.
1.3. Run
M
on
w
.
1.4. Accept.
2. Construct the description of
M
?(
x
) that operates as follows:
2.1. Accept.
3. Return <
M
?,
M
#>.
If
Oracle
exists and semidecides
L
,
C
=
Oracle
(
R
(<
M
,
w
>))
semidecides
H:
M
? accepts everything, including
. So:
<
M
,
w
>
H:
L
(
M
?) -
L
(
M
#) =
<
M
,
w
>
H:
L
(
M
?) -
L
(
M
#) =
I
N
S
D
O
U
T
Semideciding TM
H
Reduction
Enumerable
Unrestricted grammar
D
Deciding TM
A
n
B
n
C
n
Diagonalize
Lexico. enum
Reduction
L
and
L
in SD
C
o
n
t
e
x
t
-
F
r
e
e
CF grammar
A
n
B
n
Pumping
PDA
Closure
Closure
R
e
g
u
l
a
r
Regular Expression
a
*
b
*
Pumping
FSM
Closure
L
a
n
g
u
a
g
e
S
u
m
m
a
r
y
D
e
c
i
d
a
b
i
l
i
t
y
o
f
L
a
n
g
u
a
g
e
s
T
h
a
t
D
o
N
o
t
A
s
k
Q
u
e
s
t
i
o
n
s
a
b
o
u
t
T
u
r
i
n
g
M
a
c
h
i
n
e
s
U
n
d
e
c
i
d
a
b
l
e
L
a
n
g
u
a
g
e
s
T
h
a
t
D
o
N
o
t
A
s
k
Q
u
e
s
t
i
o
n
s
A
b
o
u
t
T
M
s
●
Diophantine Equations, Hilbert’s 10th Problem
●
Post Correspondence Problem
●
Tiling problems
●
Logical theories
●
Context-free languages
1. Given a CFL
L
and a string
s
, is
s
L
?
2. Given a CFL
L
, is
L
=
?
3. Given a CFL
L
, is
L
=
*?
4. Given CFLs
L
1
and
L
2
, is
L
1
=
L
2
?
5. Given CFLs
L
1
and
L
2
, is
L
1
L
2
?
6. Given a CFL
L
, is
L
context-free?
7. Given a CFL
L
, is
L
regular?
8. Given two CFLs
L
1
and
L
2
, is
L
1
L
2
=
?
9. Given a CFL
L
, is
L
inherently ambiguous?
10. Given PDAs
M
1
and
M
2
, is
M
2
a minimization of
M
1
?
11. Given a CFG
G
, is
G
ambiguous?
C
o
n
t
e
x
t
-
F
r
e
e
L
a
n
g
u
a
g
e
s
W
e
e
x
a
m
i
n
e
a
q
u
i
c
k
s
k
e
t
c
h
o
f
#
3
,
g
l
o
s
s
i
n
g
o
v
e
r
a
f
e
w
d
e
t
a
i
l
s
.
A
c
o
n
f
i
g
u
r
a
t
i
o
n
o
f
a
T
M
M
i
s
a
4
t
u
p
l
e
:
(
M
’s current state,
the nonblank portion of the tape before the read head,
the character under the read head,
the nonblank portion of the tape after the read head).
A
c
o
m
p
u
t
a
t
i
o
n
o
f
M
i
s
a
s
e
q
u
e
n
c
e
o
f
c
o
n
f
i
g
u
r
a
t
i
o
n
s
:
C
0
,
C
1
, …,
C
n
for some
n
0 such that:
●
C
0
is the initial configuration of
M
,
●
C
n
is a halting configuration of
M
, and:
●
C
0
|-
M
C
1
|-
M
C
2
|-
M
… |-
M
C
n
.
R
e
d
u
c
t
i
o
n
v
i
a
C
o
m
p
u
t
a
t
i
o
n
H
i
s
t
o
r
y
A
c
o
m
p
u
t
a
t
i
o
n
h
i
s
t
o
r
y
e
n
c
o
d
e
s
a
c
o
m
p
u
t
a
t
i
o
n
:
(
s
,
,
q
,
x
)(
q
1
,
,
a
,
z
)( …. )( …. )(
q
n
,
r
,
s
,
t
),
where
q
n
H
M
.
Example:
(
s
,
,
q
,
x
)
…
(
q
1
,
aaabbbaa
,
a
,
bbbbccc
)
(
q
2
,
aaabbbaaa
,
b
,
bbbccc
)
…
C
o
m
p
u
t
a
t
i
o
n
H
i
s
t
o
r
i
e
s
We show that CFG
ALL
is not in D by reduction from H:
R
will build
G
to generate the language
L
# composed of:
all strings in
*,
e
x
c
e
p
t
a
n
y
t
h
a
t
r
e
p
r
e
s
e
n
t
a
c
o
m
p
u
t
a
t
i
o
n
h
i
s
t
o
r
y
o
f
M
o
n
w
.
Then:
If
M
does not halt on
w
, there are no computation histories of
M
on
w
so
G
generates
* and
Oracle
will accept.
If there exists a computation history of
M
on
w
, there will be a
string that
G
will not generate;
Oracle
will reject.
C
F
G
A
L
L
=
{<
G
>
:
G
i
s
a
c
f
g
a
n
d
L
(
G
)
=
*
}
i
s
n
o
t
i
n
D
If
M
does not halt on
w
, there are no computation histories of
M
on
w
so
G
generates
* and
Oracle
will accept.
If there exists a computation history of
M
on
w
, there will be a
string that
G
will not generate;
Oracle
will reject.
Oracle
gets it backwards, so
R
must invert its response.
It is easier for
R
to build a PDA than a grammar.
So
R
will first build a PDA
P
, then convert
P
to a grammar.
B
u
t
:
For a string
s
to be a computation history of
M
on
w
:
1.
It must be a syntactically valid computation history.
2. C
0
must correspond to
M
being in its start state, with
w
on the tape, and with the read head positioned just to
the left of
w
.
3. The last configuration must be a halting configuration.
4. Each configuration after
C
0
must be derivable from the
previous one according to the rules in
M
.
C
o
m
p
u
t
a
t
i
o
n
H
i
s
t
o
r
i
e
s
a
s
S
t
r
i
n
g
s
How to test (4), that each configuration after
C
0
must be
derivable from the previous one according to the rules
in
M
?
(
q
1
,
aaaa
,
b
,
aaaa
)(
q
2
,
aaa
,
a
,
baaaa
).
Okay.
(
q
1
,
aaaa
,
b
,
aaaa
)(
q
2
,
bbbb
,
a
,
bbbb
). Not okay.
P
will have to use its stack to record the first configuration
and then compare it to the second. But what’s wrong?
C
o
m
p
u
t
a
t
i
o
n
H
i
s
t
o
r
i
e
s
a
s
S
t
r
i
n
g
s
Write every other configuration backwards.
Let
B
# be the language of computation histories of
M
except
in boustrophedon form.
•
A boustrophedon example
•
Generating boustrophedon text
T
h
e
B
o
u
s
t
r
o
p
h
e
d
o
n
V
e
r
s
i
o
n
R
(<
M
,
w
>) =
1. Construct <
P
>, where
P
accepts all strings in
B
#.
2. From
P
, construct a grammar
G
that generates
L
(
P
).
3. Return <
G
>.
If
Oracle
exists, then
C
=
Oracle
(
R
(<
M
,
w
>)) decides H:
● <
M
,
w
>
H:
M
halts on
w
. There exists a computation
history of
M
on
w
. So there is a string that
G
does not
generate.
Oracle
rejects.
R
accepts.
● <
M
,
w
>
H:
M
does not halt on
, so there exists no
computation history of
M
on
w
.
G
generates
*.
Oracle
accepts.
R
rejects.
But no machine to decide H can exist, so neither does
Oracle
.
T
h
e
B
o
u
s
t
r
o
p
h
e
d
o
n
V
e
r
s
i
o
n
G
G
=
=
{<
G
1
,
G
2
>
:
G
1
a
n
d
G
2
a
r
e
c
f
g
s
,
L
(
G
1
)
=
L
(
G
2
)
}
Proof by reduction from:
CFG
ALL
= {<G
> :
L
(
G
) =
*}:
R
is a reduction from CFG
ALL
to GG
=
defined as follows:
R
(<
M
>) =
1. Construct the description <
G
#> of a new grammar
G
#
that generates
*.
2. Return <
G
#,
G
>.
If
Oracle
exists, then
C = Oracle
(
R
(<
M
>)) decides CFG
ALL
:
●
R
is correct:
● <
G
>
CFG
ALL
:
G
is equivalent to
G
#, which generates
everything.
Oracle
accepts.
● <
G
>
CFG
ALL
:
G
is not equivalent to
G
#, which
generates everything.
Oracle
rejects.
But no machine to decide CFG
ALL
can exist, so neither does
Oracle
.
Explore the concept of Non-SD languages in the theory of computation, which are larger in number compared to SD languages. Non-SD languages involve infinite search or analyzing whether a Turing Machine will loop indefinitely. Discover examples and insights into proving languages are not SD through contractions and redactions.
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
MA/CSSE 474 Theory of Computation Non-SD Reductions
Your Questions? Previous class days' material Reading Assignments HW 15 problems Anything else Informal Poll: How is your understanding of reductions and proving undecidability? 1 2 3 4 5 6 Totally Easy for Lost me now!
Side Road with a purpose: obtainSelf From Section 25.3: In section 25.3, the author proves the existence of a very useful computable function: obtainSelf. When called as a subroutine by any Turing machine M, obtainSelf writes <M> onto M's tape. Related to quines: A quine is a computer program which takes no input and produces a copy of its own source code as its only output. Definition is from http://en.wikipedia.org/wiki/Quine_(computing)
Some quines main(){char q=34, n=10,*a="main() {char q=34,n=10,*a=%c%s%c; printf(a,q,a,q,n);}%c";printf(a,q,a,q,n);} ((lambda (x) (list x (list 'quote x))) (quote (lambda (x) (list x (list 'quote x))))) Quine's paradox and a related sentence: "Yields falsehood when preceded by its quotation" yields falsehood when preceded by its quotation. "quoted and followed by itself is a quine." quoted and followed by itself is a quine.
Non-SD Languages There is an uncountable number of non-SD languages, but only a countably infinite number of TM s (hence SD languages). The class of non-SD languages is much bigger than that of SD languages!
Non-SD Languages Intuition: Non-SD languages usually involve either infinite search (where testing each potential member could loop forever), or determining whether a TM will infinite loop. Examples: H = {<M, w> : TM M does not halt on w}. {<M> : L(M) = *}. {<M> : TM M halts on nothing}.
Proving Languages are not SD Contradiction L is the complement of an SD/D Language. Reduction from a known non-SD language
Contradiction Example Theorem: TMMIN = {<M>: Turing machine M is minimal} is not in SD. By "minimal", we mean that <M> is minimal among all encodings of TMs that are equivalent to M.
The Complement of L is in SD/D Suppose we want to know whether L is in SD and we know: L is in SD, and At least one of L or L is not in D. Then we can conclude that L is not in SD, because, if it were, it would force both itself and its complement into D, which we know cannot be true. Example: H (since ( H) = H is in SD and not in D)
Aanbn = {<M> : L(M) = AnBn} Aanbn contains strings that look like: (q00,a00,q01,a00, ), (q00,a01,q00,a10, ), (q00,a10,q01,a01, ), (q00,a11,q01,a10, ), (q01,a00,q00,a01, ), (q01,a01,q01,a10, ), (q01,a10,q01,a11, ), (q01,a11,q11,a01, ) It does not contain strings like aaabbb. But AnBn does.
Aanbn = {<M> : L(M) = AnBn} Try this one: H = {<M, w> : TM M does not halt on w} R (?Oracle) Aanbn = {<M> : L(M) = AnBn} R(<M, w>) = 1. Construct the description <M#>, where M#(x) operates as follows: 1.1. Erase the tape. 1.2. Write w on the tape. 1.3. Run M on w. 1.4. Accept. 2. Return <M#>. If Oracle exists, C = Oracle(R(<M, w>)) semidecides H:
Aanbn = {<M> : L(M) = AnBn} is not SD Also try: H = {<M, w> : TM M does not halt on w} R (?Oracle) Aanbn = {<M> : L(M) = AnBn} R(<M, w>) = 1. Construct the description <M#>, where M#(x) operates as follows: 1.1 Copy the input x to another track for later. 1.2. Erase the tape. 1.3. Write w on the tape. 1.4. Run M on w. 1.5. Put x back on the tape. 1.6. If x AnBn then accept, else loop. 2. Return <M#>. If Oracle exists, C = Oracle(R(<M, w>)) semidecides H:
Aanbn = {<M> : L(M) = AnBn} is not SD And try this one R(<M, w>) reduces H to Aanbn: 1. Construct the description <M#>: 1.1. If x AnBn then accept. Else: 1.2. Erase the tape. 1.3. Write w on the tape. 1.4. Run M on w. 1.5. Accept. 2. Return <M#>. If Oracle exists, then C = Oracle(R(<M, w>)) semidecides H:
HALL = {<M> : TM halts on *} What about: H = {<M, w> : TM M does not halt on w} R HALL = {<M> : TM halts on *} (?Oracle) Reduction Attempt 1:R(<M, w>) = 1. Construct the description <M#>, where M#(x) operates as follows: 1.1. Erase the tape. 1.2. Write w on the tape. 1.3. Run M on w. 2. Return <M#>.
There May Be No Easy Way to Flip H = {<M, w> : TM M does not halt on w} R HALL = {<M> : TM halts on *} (?Oracle) Reduction Attempt 1:R(<M, w>) = 1. Construct the description <M#>, where M#(x) operates as follows: 1.1. Erase the tape. 1.2. Write w on the tape. 1.3. Run M on w. 2. Return <M#>. If Oracle exists, C = Oracle(R(<M, w>)) semidecides H: <M, w> H: M does not halt on w, so M# gets stuck in step 1.3 and halts on nothing. Oracle does not accept. <M, w> H: M halts on w, so M# halts on everything. Oracle accepts.
HALL = {<M> : TM halts on *} R(<M, w>) reduces H to HALL: 1. Construct the description <M#>, where M#(x) operates as follows: 1.1. Copy the input x to another track for later. 1.2. Erase the tape. 1.3. Write w on the tape. 1.4. Run M on w for |x| steps or until M naturally halts. 1.5. If M naturally halted, then loop. 1.6. Else halt. 2. Return <M#>. If Oracle exists, C = Oracle(R(<M, w>)) semidecides H: <M, w> H: No matter how long x is, M will not halt in |x| steps. So, for all inputs x, M# makes it to step 1.6. So it halts on everything. Oracle accepts. <M, w> H: M halts on w in n steps. On inputs of length less than n, M# makes it to step 1.6 and halts. But on all inputs of length n or greater, M# will loop in step 1.5. Oracle does not accept.
EqTMs = {<Ma, Mb> : L(Ma) = L(Mb)} We ve already shown it s not in D. Now we show it s also not in SD.
EqTMs = {<Ma, Mb> : L(Ma) = L(Mb)} H = {<M, w> : TM M does not halt on w} R (?Oracle) EqTMs = {<Ma, Mb> : L(Ma) = L(Mb)} R(<M, w>) = 1. Construct the description <M#>: 2. Construct the description <M?>: 3. Return <M#, M?>. If Oracle exists, C = Oracle(R(<M, w>)) semidecides H: <M, w> H: <M, w> H:
EqTMs = {<Ma, Mb> : L(Ma) = L(Mb)} R(<M, w>) = 1. Construct the description <M#>: 1.1 Erase the tape. 1.2 Write w on the tape. 1.3 Run M on w. 1.4 Accept. 2. Construct the description <M?>: 1.1 Loop. 3. Return <M#, M?>. If Oracle exists, C = Oracle(R(<M, w>)) semidecides H: M? halts on nothing. <M, w> H: M does not halt on w, so M# gets stuck in step 1.3 and halts on nothing. Oracle accepts. <M, w> H: M halts on w, so M# halts on everything. Oracle does not accept.
The Details Matter L1 = {<M>: M has an even number of states}. L2 = {<M>: |<M>| is even}. L3 = {<M>: |L(M)| is even}. L4 = {<M>: M accepts all even length strings}.
Accepting, Rejecting, Halting, and Looping Consider : L1 = {<M, w>: M rejects w}. L2 = {<M, w>: M does not halt on w}. L3 = {<M, w>: M is a deciding TM and rejects w}.
What About These? L1 = {a}. L2 = {<M> : M accepts a}. L3 = {<M> : L(M) = {a}}.
The Problem View The Language View Status Does TM M have an even number of states? Does TM M halt on w? {<M> : M has an even number of states} H = {<M, w> : M halts on w} D SD/D H = {<M> : M halts on } Does TM M halt on the empty tape? SD/D Is there any string on which TM M halts? HANY = {<M> : there exists at least one string on which TM M halts } HALL = {<M> : M halts on *} SD/D SD Does TM M halt on all strings? Does TM M accept w? A = {<M, w> : M accepts w} SD/D Does TM M accept ? A = {<M> : M accepts } SD/D Is there any string that TM M accepts? AANY {<M> : there exists at least SD/D one string that TM M accepts }
AALL = {<M> : L(M) = *} SD Does TM M accept all strings? SD Do TMs Ma and Mb accept the same languages? EqTMs = {<Ma, Mb> : L(Ma) = L(Mb)} SD Does TM M not halt on any string? H ANY = {<M> : there does not exist any string on which M halts} {<M> : TM M does not halt on input <M>} TMMIN = {<M>: M is minimal} SD Does TM M not halt on its own description? Is TM M minimal? SD SD Is the language that TM M accepts regular? TMreg = {<M> : L(M) is regular} SD Does TM M accept the language AnBn? Aanbn = {<M> : L(M) = AnBn}
Language Summary IN SD H OUT Reduction Semideciding TM Enumerable Unrestricted grammar Deciding TM Lexico. enum L and L in SD AnBnCn D Diagonalize Reduction CF grammar PDA Closure Context-Free AnBn Pumping Closure Regular Expression a*b* FSM Regular Pumping Closure
Decidability of Languages That Do Not Ask Questions about Turing Machines
Undecidable Languages That Do Not Ask Questions About TMs Diophantine Equations, Hilbert s 10th Problem Post Correspondence Problem Tiling problems Logical theories Context-free languages
Context-Free Languages 1. Given a CFL L and a string s, is s L? 2. Given a CFL L, is L = ? 3. Given a CFL L, is L = *? 4. Given CFLs L1 and L2, is L1 = L2? 5. Given CFLs L1 and L2, is L1 L2 ? 6. Given a CFL L, is L context-free? 7. Given a CFL L, is L regular? 8. Given two CFLs L1 and L2, is L1 L2 = ? 9. Given a CFL L, is L inherently ambiguous? 10. Given PDAs M1 and M2, is M2 a minimization of M1? 11. Given a CFG G, is G ambiguous? We examine a quick sketch of #3, glossing over a few details.
Reduction via Computation History A configuration of a TM M is a 4 tuple: ( M s current state, the nonblank portion of the tape before the read head, the character under the read head, the nonblank portion of the tape after the read head). A computation of M is a sequence of configurations: C0, C1, , Cn for some n 0 such that: C0 is the initial configuration of M, Cn is a halting configuration of M, and: C0 |-MC1 |-MC2 |-M |-MCn.
Computation Histories A computation history encodes a computation: (s, , q, x)(q1, , a, z)( . )( . )(qn, r, s, t), where qn HM. Example: (s, , q, x) (q1, aaabbbaa, a, bbbbccc) (q2, aaabbbaaa, b, bbbccc)
CFGALL = {<G> : G is a cfg and L(G) = *} is not in D We show that CFGALL is not in D by reduction from H: R will build G to generate the language L# composed of: all strings in *, except any that represent a computation history of M on w. Then: If M does not halt on w, there are no computation histories of M on w so G generates * and Oracle will accept. If there exists a computation history of M on w, there will be a string that G will not generate; Oracle will reject.
But: If M does not halt on w, there are no computation histories of M on w so G generates * and Oracle will accept. If there exists a computation history of M on w, there will be a string that G will not generate; Oracle will reject. Oracle gets it backwards, so R must invert its response. It is easier for R to build a PDA than a grammar. So R will first build a PDA P, then convert P to a grammar.
Computation Histories as Strings For a string s to be a computation history of M on w: 1. It must be a syntactically valid computation history. 2. C0 must correspond to M being in its start state, with w on the tape, and with the read head positioned just to the left of w. 3. The last configuration must be a halting configuration. 4. Each configuration after C0 must be derivable from the previous one according to the rules in M.
Computation Histories as Strings How to test (4), that each configuration after C0 must be derivable from the previous one according to the rules in M? (q1, aaaa, b, aaaa)(q2, aaa, a, baaaa). Okay. (q1, aaaa, b, aaaa)(q2, bbbb, a, bbbb). Not okay. P will have to use its stack to record the first configuration and then compare it to the second. But what s wrong?
The Boustrophedon Version Write every other configuration backwards. Let B# be the language of computation histories of M except in boustrophedon form. A boustrophedon example Generating boustrophedon text
The Boustrophedon Version R(<M, w>) = 1. Construct <P>, where P accepts all strings in B#. 2. From P, construct a grammar G that generates L(P). 3. Return <G>. If Oracle exists, then C = Oracle(R(<M, w>)) decides H: <M, w> H: M halts on w. There exists a computation history of M on w. So there is a string that G does not generate. Oracle rejects. R accepts. <M, w> H: M does not halt on , so there exists no computation history of M on w. G generates *. Oracle accepts. R rejects. But no machine to decide H can exist, so neither does Oracle.
GG= = {<G1, G2> : G1 and G2 are cfgs, L(G1) = L(G2)} CFGALL = {<G> : L(G) = *}: Proof by reduction from: R is a reduction from CFGALL to GG= defined as follows: R(<M>) = 1. Construct the description <G#> of a new grammar G# that generates *. 2. Return <G#, G>. If Oracle exists, then C = Oracle(R(<M>)) decides CFGALL: R is correct: <G > CFGALL: G is equivalent to G#, which generates everything. Oracle accepts. <G > CFGALL: G is not equivalent to G#, which generates everything. Oracle rejects. But no machine to decide CFGALL can exist, so neither does Oracle.
