## CS310 : Automata Theory 2019

### Lecture 28: Reductions

Instructor: S. Akshay

IITB, India

14-03-2019

### Recap of previous lecture

Regular (Decidable (Recursively Enumerable( All languages DFA/NFA <Algorithms/Halting TM<Semi-algorithms/TM Properties

1. There exist languages that are not R.E.

2. There exist languages that are R.E but are undecidable.

Eg. universal TM langL^{A}_{TM} ={hM,wi |M is a TM andM accepts w}
3. Decidable languages are closed under complementation.

4. L is decidable iffL isR.E andL is also R.E.

### The halting problem

The halting problem for Turing Machines is undecidable Does a given Turing machine halt on a given input?

I L^{HALT}_{TM} ={hM,wi |M is a TM andM halts on inputw}.

Proof: Suppose there exists TMH deciding L^{HALT}_{TM} , then construct a TMD
s.t., on inputhM,wi:

I runs TMH on inputhM,wi I if H rejects then reject.

I if H accepts, then simulate M onw until it halts.
I if at halting M has acceptedw, accept, else reject.
ButD decidesL^{A}_{TM} which is undecidable. A contradiction.
This proof strategy is called a reduction.

### The halting problem

The halting problem for Turing Machines is undecidable Does a given Turing machine halt on a given input?

I L^{HALT}_{TM} ={hM,wi |M is a TM andM halts on inputw}.

Proof: Suppose there exists TM H decidingL^{HALT}_{TM} , then construct a TMD
s.t., on inputhM,wi:

I runs TMH on inputhM,wi I if H rejects then reject.

I if H accepts, then simulate M onw until it halts.

I if at halting M has acceptedw, accept, else reject.

But D decidesL^{A}_{TM} which is undecidable. A contradiction.

This proof strategy is called a reduction.

### The halting problem

The halting problem for Turing Machines is undecidable Does a given Turing machine halt on a given input?

I L^{HALT}_{TM} ={hM,wi |M is a TM andM halts on inputw}.

Proof: Suppose there exists TM H decidingL^{HALT}_{TM} , then construct a TMD
s.t., on inputhM,wi:

I runs TMH on inputhM,wi I if H rejects then reject.

I if H accepts, then simulate M onw until it halts.

I if at halting M has acceptedw, accept, else reject.

But D decidesL^{A}_{TM} which is undecidable. A contradiction.

### Reduction from the acceptance problem

I L^{HALT}_{TM} ={hM,wi |M is a TM andM halts on inputw}.

hM,wi H

M Acc w

Rej Rej

Rej Rej Acc Acc

### Some more undecidable problems

The emptiness problem for TMs

Does a given Turing machine accept any word?

I L^{∅}_{TM} ={hMi |M is a TM andL(M) =∅}.

Proof:

I For contradiction, assume its decidable, say by TM R.
I DefineM_{1} which on input x,

I ifx6=w, it rejects

I ifx=w, runM onw and accept ifM accepts. I ConstructS which decidesATM: Given inputhM,wi,

I ConstructM1on tape fromM andw, I RunR on inputhM1i.

I IfR accepts,reject; ifR rejects thenaccept.

### Some more undecidable problems

The emptiness problem for TMs is undecidable Does a given Turing machine accept any word?

I L^{∅}_{TM} ={hMi |M is a TM andL(M) =∅}.

Proof:

I For contradiction, assume its decidable, say by TM R.

I DefineM_{1} which on input x,
I ifx6=w, it rejects

I ifx=w, runM onw and accept ifM accepts. I ConstructS which decidesATM: Given inputhM,wi,

I ConstructM1on tape fromM andw, I RunR on inputhM1i.

I IfR accepts,reject; ifR rejects thenaccept.

### Some more undecidable problems

The emptiness problem for TMs is undecidable Does a given Turing machine accept any word?

I L^{∅}_{TM} ={hMi |M is a TM andL(M) =∅}.

Proof:

I For contradiction, assume its decidable, say by TM R.

I DefineM_{1} which on input x,
I ifx6=w, it rejects

I ifx=w, runM onw and accept ifM accepts.

I ConstructS which decidesATM: Given inputhM,wi, I ConstructM1on tape fromM andw,

I RunR on inputhM1i.

I IfR accepts,reject; ifR rejects thenaccept.

### Some more undecidable problems

The emptiness problem for TMs is undecidable Does a given Turing machine accept any word?

I L^{∅}_{TM} ={hMi |M is a TM andL(M) =∅}.

Proof:

I For contradiction, assume its decidable, say by TM R.

I DefineM_{1} which on input x,
I ifx6=w, it rejects

I ifx=w, runM onw and accept ifM accepts.

I ConstructS which decidesATM: Given inputhM,wi,

I ConstructM1on tape fromM andw, I RunR on inputhM1i.

I IfR accepts,reject; ifR rejects thenaccept.

### Some more undecidable problems

The emptiness problem for TMs is undecidable Does a given Turing machine accept any word?

I L^{∅}_{TM} ={hMi |M is a TM andL(M) =∅}.

Proof:

I For contradiction, assume its decidable, say by TM R.

I DefineM_{1} which on input x,
I ifx6=w, it rejects

I ifx=w, runM onw and accept ifM accepts.

I ConstructS which decidesATM: Given inputhM,wi, I ConstructM1on tape fromM andw,

I RunR on inputhM1i.

I IfR accepts,reject; ifR rejects thenaccept.

### Some more undecidable problems

The emptiness problem for TMs is undecidable Does a given Turing machine accept any word?

I L^{∅}_{TM} ={hMi |M is a TM andL(M) =∅}.

Proof:

I For contradiction, assume its decidable, say by TM R.

I DefineM_{1} which on input x,
I ifx6=w, it rejects

I ifx=w, runM onw and accept ifM accepts.

I ConstructS which decidesATM: Given inputhM,wi, I ConstructM1on tape fromM andw,

I IfR accepts,reject; ifR rejects thenaccept.

### Some more undecidable problems

The emptiness problem for TMs is undecidable Does a given Turing machine accept any word?

I L^{∅}_{TM} ={hMi |M is a TM andL(M) =∅}.

Proof:

I For contradiction, assume its decidable, say by TM R.

I DefineM_{1} which on input x,
I ifx6=w, it rejects

I ifx=w, runM onw and accept ifM accepts.

I ConstructS which decidesATM: Given inputhM,wi, I ConstructM1on tape fromM andw,

I RunR on inputhM1i.

reject; ifR rejects thenaccept.

### Some more undecidable problems

The emptiness problem for TMs is undecidable Does a given Turing machine accept any word?

I L^{∅}_{TM} ={hMi |M is a TM andL(M) =∅}.

Proof:

I For contradiction, assume its decidable, say by TM R.

I DefineM_{1} which on input x,
I ifx6=w, it rejects

I ifx=w, runM onw and accept ifM accepts.

I ConstructS which decidesATM: Given inputhM,wi, I ConstructM1on tape fromM andw,

### Some more undecidable problems

The regularity problem for TMs

Does a given Turing machine accept a regular language?

I L^{REG}_{TM} ={hMi |M is a TM andL(M) is a regular language}.

Proof: By contradiction, assumeR decides Reg. We define S I S = On input hM,wi;

I construct TMM2as follows: M2on input x does the foll:

I ifx has the form 0^{n}1^{n}, accept.

I If not, runM onw and accept ifM acceptsw. I RunR onhM2i.

I IfR accepts,accept; ifR rejects,reject.

### Some more undecidable problems

The regularity problem for TMs

Does a given Turing machine accept a regular language?

I L^{REG}_{TM} ={hMi |M is a TM andL(M) is a regular language}.

Proof: By contradiction, assume R decides Reg. We define S

I S = On input hM,wi;

I construct TMM2as follows: M2on input x does the foll:

I ifx has the form 0^{n}1^{n}, accept.

I If not, runM onw and accept ifM acceptsw. I RunR onhM2i.

I IfR accepts,accept; ifR rejects,reject.

### Some more undecidable problems

The regularity problem for TMs

Does a given Turing machine accept a regular language?

I L^{REG}_{TM} ={hMi |M is a TM andL(M) is a regular language}.

Proof: By contradiction, assume R decides Reg. We define S I S = On input hM,wi;

I construct TMM2as follows:

M2on input x does the foll:
I ifx has the form 0^{n}1^{n}, accept.

I If not, runM onw and accept ifM acceptsw. I RunR onhM2i.

I IfR accepts,accept; ifR rejects,reject.

### Some more undecidable problems

The regularity problem for TMs

Does a given Turing machine accept a regular language?

I L^{REG}_{TM} ={hMi |M is a TM andL(M) is a regular language}.

Proof: By contradiction, assume R decides Reg. We define S I S = On input hM,wi;

I construct TMM2as follows:

M_{2}on input x does the foll:

I ifx has the form 0^{n}1^{n}, accept.

I If not, runM onw and accept ifM acceptsw.

I RunR onhM2i.

I IfR accepts,accept; ifR rejects,reject.

### Some more undecidable problems

The regularity problem for TMs

Does a given Turing machine accept a regular language?

I L^{REG}_{TM} ={hMi |M is a TM andL(M) is a regular language}.

Proof: By contradiction, assume R decides Reg. We define S I S = On input hM,wi;

I construct TMM2as follows:

M_{2}on input x does the foll:

I ifx has the form 0^{n}1^{n}, accept.

I If not, runM onw and accept ifM acceptsw. I RunR onhM2i.

I IfR accepts,accept; ifR rejects,reject.

### Some more undecidable problems

The regularity problem for TMs

Does a given Turing machine accept a regular language?

I L^{REG}_{TM} ={hMi |M is a TM andL(M) is a regular language}.

Proof: By contradiction, assume R decides Reg. We define S I S = On input hM,wi;

I construct TMM2as follows:

M_{2}on input x does the foll:

I ifx has the form 0^{n}1^{n}, accept.

I If not, runM onw and accept ifM acceptsw. I RunR onhM2i.

### The principle of reduction

Reduction: An algorithm (TM!) to convert instances of one problem to another

I Convert instance of P_{1} to instance ofP_{2}
I answer is yes forP_{1} iff answer is yes forP_{2}

I then P_{2} is at least as hard asP_{1}, i.e.,
I ifP_{1}is not decidable, neither isP_{2}
I ifP_{1}is not r.e., neither isP_{2}.

I note that every instance ofP_{2} need not be covered!

### The principle of reduction

Reduction: An algorithm (TM!) to convert instances of one problem to another

I Convert instance of P_{1} to instance ofP_{2}
I answer is yes forP_{1} iff answer is yes forP_{2}
I then P_{2} is at least as hard asP_{1}, i.e.,

I ifP_{1}is not decidable, neither isP_{2}
I ifP_{1}is not r.e., neither isP_{2}.

I note that every instance ofP_{2} need not be covered!

### The principle of reduction

Reduction: An algorithm (TM!) to convert instances of one problem to another

I Convert instance of P_{1} to instance ofP_{2}
I answer is yes forP_{1} iff answer is yes forP_{2}
I then P_{2} is at least as hard asP_{1}, i.e.,

I ifP_{1}is not decidable, neither isP_{2}

I ifP_{1}is not r.e., neither isP_{2}.

I note that every instance ofP_{2} need not be covered!

### The principle of reduction

Reduction: An algorithm (TM!) to convert instances of one problem to another

I Convert instance of P_{1} to instance ofP_{2}
I answer is yes forP_{1} iff answer is yes forP_{2}
I then P_{2} is at least as hard asP_{1}, i.e.,

I ifP_{1}is not decidable, neither isP_{2}
I ifP_{1}is not r.e., neither isP_{2}.

I note that every instance ofP_{2} need not be covered!

### The principle of reduction

Reduction: An algorithm (TM!) to convert instances of one problem to another

_{1} to instance ofP_{2}
I answer is yes forP_{1} iff answer is yes forP_{2}
I then P_{2} is at least as hard asP_{1}, i.e.,

I ifP_{1}is not decidable, neither isP_{2}
I ifP_{1}is not r.e., neither isP_{2}.

I note that every instance ofP_{2} need not be covered!

### Some more undecidable problems

The regularity problem for TMs

Does a given Turing machine accept a regular language?

I L^{EQ}_{TM} ={hM_{1},M2i |M are TMs andL(M1) =L(M2)}.

Proof: Exercise.

### Some more undecidable problems

The regularity problem for TMs

Does a given Turing machine accept a regular language?

I L^{EQ}_{TM} ={hM_{1},M2i |M are TMs andL(M1) =L(M2)}.

Proof: Exercise.