Scribd
Upload
66 views

Formal Languages, Automata and Computability

This document discusses reductions and undecidability proofs. It shows that the halting problem (HALTTM) is undecidable by reducing the acceptance problem (ATM) to it. Specifically, it constructs a Turing machine D that on input (M,w) simulates a hypothetical decision machine H for ATM. It then shows that D can construct an instance (DH,DH) that H would fail to classify correctly, proving no such H can exist and ATM is undecidable. Similarly, it reduces various language problems like the emptiness problem (ETM) to ATM, showing their undecidability by reducing ATM which is already known to be undecidable. The key concept

Uploaded by

Mahnoor Khandwani
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
66 views

Formal Languages, Automata and Computability

This document discusses reductions and undecidability proofs. It shows that the halting problem (HALTTM) is undecidable by reducing the acceptance problem (ATM) to it. Specifically, it constructs a Turing machine D that on input (M,w) simulates a hypothetical decision machine H for ATM. It then shows that D can construct an instance (DH,DH) that H would fail to classify correctly, proving no such H can exist and ATM is undecidable. Similarly, it reduces various language problems like the emptiness problem (ETM) to ATM, showing their undecidability by reducing ATM which is already known to be undecidable. The key concept

Uploaded by

Mahnoor Khandwani
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
You are on page 1/ 28

15-453

FORMAL LANGUAGES,
AUTOMATA AND
COMPUTABILITY
UNDECIDABILITY II:
REDUCTIONS
ATM = { (M,w) | M is a TM that accepts string w }
ATM is undecidable: (constructive proof & subtle)
Assume machine H semi-decides ATM
Accept if M accepts w
H( (M,w) ) =
Rejects or loops otherwise

Construct a new TM DH as follows: on input M,


run H on (M,M) and output the “opposite” of H
whenever possible.
Reject if D
MH accepts D MH
(i.e. if H( MH , D
D MH ) = Accept)

Accept if D MH rejects DMH


DH ( D
MH ) =
MH , D
(i.e. if H( D MH ) = Reject)

loops if D MH loops on D MH
(i.e. if H( D
MH , DMH ) loops)

Note: There is no contradiction here!


DH loops on DH
We can effectively construct an instance which
does not belong to ATM (namely, (DH, DH) )
but H fails to tell us that.
That is:
Given any semi-decision machine H for ATM
(and thus a potential decision machine for ATM ),
we can effectively construct an instance which
does not belong to ATM (namely, ( DH, DH ))
but H fails to tell us that.
So H cannot be a decision machine for ATM
THE HALTING PROBLEM
HALTTM = { (M,w) | M is a TM that halts on string w }
Theorem: HALTTM is undecidable
Proof: Assume, for a contradiction, that TM H
decides HALTTM
We use H to construct a TM D that decides ATM

On input (M,w), D runs H on (M,w)


If H rejects then reject
If H accepts, run M on w until it halts:
Accept if M accepts and
Reject if M rejects
(M,w)

(M,w)
If M halts
D H Does M
w
halt on w?

If M doesn’t M
halt: REJECT
In most cases, we will show that a
language L is undecidable by showing
that if it is decidable, then so is ATM

We reduce deciding ATM to deciding


the language in question
ATM “<” L
So, ATM “<” HaltTM
Is HaltTM “<” ATM ?
ETM = { M | M is a TM and L(M) =  }
Theorem: ETM is undecidable
Proof: Assume, for a contradiction, that TM Z
decides ETM Use Z as a subroutine to decide ATM
Algorithm for deciding ATM: On input (M,w):

1. Create Mw
Mw
s If s  w, REJECT
If s = w, run M(w)

So, L (Mw) =   M(w) does not accept


L (Mw)    M(w) accepts
2. Run Z on Mw
Mw
s If s  w, REJECT
If s = w, run M(w) (M,w)
So, L (Mw) =   M(w)
does not accept N Mw

Decision Machine
Z L(M w) ==?
L(N)
?
for ATM
Accepts if M does not accept w
Rejects, otherwise
REVERSE accept/reject
REGULARTM = { M | M is a TM and L(M) is regular}
Theorem: REGULARTM is undecidable
Proof: Assume, for a contradiction, that TM R
decides REGULARTM
Mw
s If s = 0n1n, accept
Else run M(w)

L(Mw) = Σ* if M(w) accepts


N Mw
{0n1n } otherwise
L(Mw) is regular  M(w) accepts
R IsIsL(M
L(N) regular?
w) regular?

Yes  M accepts w
ALLPDA = { P | P is a PDA and L(P) = Σ* }
Theorem: ALLPDA is undecidable
Proof: Assume, for a contradiction, that TM A
decides ALLPDA

We use A to decide ATM

More subtle construction


Idea! If M(w) does not accept, then there is no
Idea!
accepting computation for M on input w. Then any
string of 0’s and 1’s will fail to be (a code for) an
accepting computation. So, given (M, w) construct a
PDA that accepts non-accepting computations of M on w.
Thus, M(w) does not accept  L(P) = Σ*
CONFIGURATIONS

11010q700110
q7

1 1 0 1 0 0 0 1 1 0
COMPUTATION HISTORIES
An accepting computation history is a
sequence of configurations C1,C2,…,Ck, where
1. C1 is the start configuration,
2. Ck is an accepting configuration,
3. Each Ci follows from Ci-1

An rejecting computation history is a


sequence of configurations C1,C2,…,Ck, where
1. C1 is the start configuration,
2. Ck is a rejecting configuration,
3. Each Ci follows from Ci-1
M accepts w
if and only if
there exists an accepting
computation history
that starts with C1=q0w
ALLPDA = { P | P is a PDA and L(P) = Σ* }
Theorem: ALLPDA is undecidable
Proof: Assume, for a contradiction, that TM A
decides ALLPDA

We use A to decide ATM

On input (M,w), construct a PDA P that accepts


Σ* if and only if M does not accept w

P will recognize all strings that are NOT


accepting computation histories for M on w
P will recognize all strings (read as sequences
of configurations) that:
1. Do not start with C1
2. Do not end with an accepting configuration
3. Where some Ci does not properly yield Ci+1

ε,ε → ε ε,ε → ε

ε,ε → ε

Non-deterministic checks for 1, 2, and 3.


P recognizes all strings except:

#C1# C2R #C3 #C4R #C5 #C6R #….# Ck

If k is odd, put Ck on stack and see if Ck+1R


follows properly:
For example,
If =uaqibv and  (qi,b) = (qj,c,R),
then Ck properly yields Ck+1  Ck+1 = uacqjv
P recognizes all strings except:

#C1# C2R #C3 #C4R #C5 #C6R #….# Ck

If k is odd, put Ck on stack and see if Ck+1R


follows properly:
For example,
If =uaqibv and  (qi,b) = (qj,c,L),
then Ck properly yields Ck+1  Ck+1 = uqjacv
P recognizes all strings except:

#C1# C2R #C3 #C4R #C5 #C6R #….# Ck

If k is even, put CkR on stack and see if Ck+1


follows properly:
For example,
If =uaqibv and  (qi,b) = (qj,c,L),
then Ck properly yields Ck+1  Ck+1 = uqjacv
ALLPDA = { P | P is a PDA and L(P) = Σ* }
Theorem: ALLPDA is undecidable
Proof: Assume, for a contradiction, that TM A
decides ALLPDA

We use A to decide ATM

On input (M,w), construct a PDA P that accepts


Σ* if and only if M does not accept w

P will recognize all strings that are NOT


accepting computation histories for M on w
MAPPING REDUCIBILITY
f : Σ*  Σ* is a computable function if some
Turing machine M, on every input w, halts with
just f(w) on its tape
A language A is mapping reducible to
language B, written A  m B, if there is a
computable function (“coding”) f : Σ*  Σ*,
where for every w,
w  A  f(w) 
B
f is called a reduction from A to B
A B
f

f
Theorem: If A  m B and B is decidable,
then A is decidable

Proof: Let M decide B and let f be a


reduction from A to B

We build a machine N that decides A as follows:


On input w:
1. Compute f(w)
2. Run M on f(w)
All undecidability proofs from today
can be seen as constructing an f that
reduces ATM to the proper language

Exercise. Construct such an f in each


case. (Hint. Sometimes you have to
consider the complement of the
language. )
All undecidability proofs from today
can be seen as constructing an f that
reduces ATM to the proper language

ATM  m HALTTM :
Map (M, w)  (M’, w)
where M’(w) = M(w) if M(w) accepts
loops otherwise

So (M, w)  ATM  (M’, w)  HALTTM


Read chapter 5.1-5.3 of the book for next time

You might also like