F ORMAL L ANGUAGES , AUTOMATA AND
C OMPUTATION
R EDUCIBILITY
( L ECTURE 16) S LIDES FOR 15-453 S PRING 2011 1 / 20
T HE L ANDSCAPE OF THE C HOMSKY H IERARCHY
( L ECTURE 16) S LIDES FOR 15-453 S PRING 2011 2 / 20
R EDUCIBILITY
A reduction is a way of converting one problem to another problem, so
that the solution to the second problem can be used to solve the first
problem.
Finding the area of a rectangle, reduces to measuring its width and height
Solving a set of linear equations, reduces to inverting a matrix.
Reducibility involves two problems A and B.
If A reduces to B, you can use a solution to B to solve A
When A is reducible to B solving A can not be “harder” than solving B.
If A is reducible to B and B is decidable, then A is also decidable.
If A is undecidable and reducible to B, then B is undecidable.
( L ECTURE 16) S LIDES FOR 15-453 S PRING 2011 3 / 20
P ROVING U NDECIDABILITY VIA R EDUCTIONS
T HEOREM 5.1
HALTTM = {hM, wi | M is a TM and M halts on input w} is undecidable.
P ROOF
Use the idea that “ If A is undecidable and reducible to B, then B is
undecidable.”
Suppose R decides HALTTM . We construct S to decide ATM .
S = “On input hM, wi
1 Run R on input hM, wi.
2 If R rejects reject.
3 If R accepts, simulate M on w until it halts.
4 If M has accepted, accept; If M has rejected, reject.”
Since ATM is reduced to HALTTM , HALTTM is undecidable.
( L ECTURE 16) S LIDES FOR 15-453 S PRING 2011 4 / 20
P ROVING U NDECIDABILITY VIA R EDUCTIONS
T HEOREM 5.2
ETM = {hMi | M is a TM and L(M) = Φ} is undecidable.
Suppose R decides ETM . We try to construct S to decide ATM using R.
Note that S takes hM, wi as input.
One idea is to run R on hMi to check if M accepts some string or not –
but that that does not tell us if M accepts w.
Instead we modify M to M1 . M1 rejects all strings other than w but on w,
it does what M does.
Now we can check if L(M1 ) = Φ.
( L ECTURE 16) S LIDES FOR 15-453 S PRING 2011 5 / 20
P ROVING U NDECIDABILITY VIA R EDUCTIONS
T HEOREM 5.2
ETM = {hMi | M is a TM and L(M) = Φ} is undecidable.
P ROOF
For any w define M1 as
M1 = “On input x:
1 6 w, reject.
If x =
2 If x = w, run M on input w and accept if M does.”
Note that M1 either accepts w only or nothing!
( L ECTURE 16) S LIDES FOR 15-453 S PRING 2011 6 / 20
P ROVING U NDECIDABILITY VIA R EDUCTIONS
P ROOF CONTINUED
Assume R decides ETM
S defines below uses R to decide on ATM
S = “On input hM, wi
1 Use hM, wi to construct M1 above.
2 Run R on input hM1 i
3 If R accepts, reject, if R rejects, accept.
So, if R decides M1 is empty,
then M does NOT accept w,
else M accepts w.
If R decides ETM then S decides ATM – Contradiction.
( L ECTURE 16) S LIDES FOR 15-453 S PRING 2011 7 / 20
T ESTING FOR R EGULARITY ( OR OTHER PROPERTIES )
Can we find out if a language accepted by a Turing machine M is
accepted by a simpler computational model?
Is the language of a TM actually a regular language? (REGULARTM )
Is the language of a TM actually a CFL? (CFLTM )
Does that language of a TM have an “interesting” property?
Rice’s Theorem.
( L ECTURE 16) S LIDES FOR 15-453 S PRING 2011 8 / 20
T ESTING FOR R EGULARITY
REGULARTM = {hMi | M is a TM and L(M) is a regular language } is
undecidable.
P ROOF I DEA
We assume REGULARTM is decidable by a TM R and use this
assumption to construct a TM S that decides ATM .
The basic idea is for S to take as input hMi and modify M into M2 so that
the resulting TM recognizes a regular language if and only if M accepts
w.
M2
accepts {0n 1n | n ≥ 0} if M does not accept w,
but recognizes Σ∗ if M accepts w.
( L ECTURE 16) S LIDES FOR 15-453 S PRING 2011 9 / 20
T ESTING FOR R EGULARITY
P ROOF I DEA – CONTINUED
M2 accepts {0n 1n | n ≥ 0} if M does not accept w, but recognizes Σ∗ if M
accepts w.
What does M2 look like?
M2 = “On input x
1 If x has the form 0n 1n , accept.
2 If x does not have this form, run M on input w and accept if M accepts w.”
All strings x (that is Σ∗ ) are accepted if M accepts w.
( L ECTURE 16) S LIDES FOR 15-453 S PRING 2011 10 / 20
T ESTING FOR R EGULARITY
( L ECTURE 16) S LIDES FOR 15-453 S PRING 2011 11 / 20
T ESTING FOR R EGULARITY
P ROOF
S = “On input hM, wi, where M is a TM and w is a string:
1 Construct the following TM M2 .
2 M2 = “On input x
1. If x has the form 0n 1n , accept.
2. If x does not have this form, run M on input w and accept if M accepts w.”
3 Run R on hM2 i
4 If R accepts, accept, if R rejects, reject.
So, R will say M2 is a regular language, if M accepts w.
S says “M accepts w” if R decides M2 is regular – Contradiction!
( L ECTURE 16) S LIDES FOR 15-453 S PRING 2011 12 / 20
T ESTING FOR L ANGUAGE E QUALITY
T HEOREM 5.4
EQTM = {hM1 , M2 i | M1 and M2 are TMs and L(M1 ) = L(M2 )} is undecidable.
P ROOF I DEA
We reduce ETM (the emptiness problem) to this problem.
If one of the languages is empty, determining equality is the same as
determining if the second language is empty!
In fact, the ETM is a special case of the EQTM problem!!
( L ECTURE 16) S LIDES FOR 15-453 S PRING 2011 13 / 20
T ESTING FOR L ANGUAGE E QUALITY
T HEOREM 5.4
EQTM = {hM1 , M2 i | M1 and M2 are TMs and L(M1 ) = L(M2 )} is undecidable.
P ROOF
Assume R decides EQTM
S = “On input hMi where M is a TM:
1 Run R on input hM, M1 i where M1 is a TM that rejects all inputs.
2 If R accepts, accept; if R rejects reject”
Thus, if R decides EQTM , then S decides ETM
But ETM is undecidable, so EQTM , must be undecidable.
( L ECTURE 16) S LIDES FOR 15-453 S PRING 2011 14 / 20
R EDUCTIONS VIA C OMPUTATION H ISTORIES
An accepting computation history for a TM is a sequence of
configurations
C1 , C2 , . . . , Cl
such that
C1 is the start configuration for input w
Cl is an accepting configuration, and
each Ci follows legally from the preceding configuration.
A rejecting computation history is defined similarly.
Computation histories are finite sequences – if M does not halt on w,
there is no computation history.
Deterministic v.s nondeterministic computation histories.
( L ECTURE 16) S LIDES FOR 15-453 S PRING 2011 15 / 20
L INEAR B OUNDED AUTOMATON
Suppose we cripple a TM so that the head never moves outside the
boundaries of the input string.
Such a TM is called a linear bounded automaton (LBA)
Despite their memory limitation, LBAs are quite powerful.
L EMMA
Let M be a LBA with q states, g symbols in the tape alphabet. There are
exactly qng n distinct configurations for a tape of length n.
P ROOF .
The machine can be in one of q states.
The head can be on one of the n cells.
At most g n distinct strings can occur on the tape.
( L ECTURE 16) S LIDES FOR 15-453 S PRING 2011 16 / 20
D ECIDABILITY OF LBA P ROBLEMS
T HEOREM 5.9
ALBA = {hM, wi | M is an LBA that accepts string w} is decidable.
P ROOF I DEA
We simulate LBA M on w with a TM L (which is NOT an LBA!)
If during simulation M accepts or rejects, we accept or reject accordingly.
What happens if the LBA M loops?
Can we detect if it loops?
M has a finite number of configurations.
If it repeats any configuration during simulation, it is in a loop.
If M is in a loop, we will know this after a finite number of steps.
So if the LBA M has not halted by then, it is looping.
( L ECTURE 16) S LIDES FOR 15-453 S PRING 2011 17 / 20
D ECIDABILITY OF LBA P ROBLEMS
T HEOREM 5.9
ALBA = {hM, wi | M is an LBA that accepts string w} is decidable.
P ROOF
The following TM decides ALBA .
L = “On input hM, wi
1 Simulate M on for qng n steps or until it halts.
2 If M has halted, accept if it has accepted, and reject if it has rejected. If it
has NOT halted, reject.”
LBAs and TMs differ in one important way. ALBA is decidable.
( L ECTURE 16) S LIDES FOR 15-453 S PRING 2011 18 / 20
C OMPUTATION OVER “C OMPUTATION H ISTORIES ”
Now for a really wild and crazy idea!
Consider an accepting computation history of a TM M, C1 , C2 , . . . , Cl
Note that each Ci is a string.
Consider the string
#| {z }#| {z }#| {z }#···#| {z }#
C1 C2 C3 Cl
The set of all valid accepting histories is also a language!!
This string has length m and an LBA B can check if this is a valid
computation history for a TM M accepting w.
Check if C1 = q0 w1 w2 · · · wn
Check if Cl = · · · qaccept · · ·
Check if each Ci+1 follows from Ci legally.
Note that B is not constructed for the purpose of running it on any input!
If L(B) 6= Φ then M accepts w
( L ECTURE 16) S LIDES FOR 15-453 S PRING 2011 19 / 20
D ECIDABILITY OF LBA P ROBLEMS
T HEOREM 5.10
ELBA = {hMi | M is an LBA and L(M) = Φ} is undecidable.
P ROOF .
Suppose TM R decides ELBA , we can construct a TM S which decides
ATM
S = “On input hM, wi, where M is a TM and w is a string
1 Construct LBA B from M and w as described earlier.
2 Run R on hBi.
3 If R rejects, accept; if R accepts, reject.”
So if R says L(B) = Φ, the M does NOT accept w.
If R says L(B) 6= Φ, the M accepts w.
But, ATM is undecidable – contradiction.
( L ECTURE 16) S LIDES FOR 15-453 S PRING 2011 20 / 20
