The halting problem

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

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}.

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₁ 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₁ 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₁ 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₁ 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₁ 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₁ 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₁ 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₁ 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ⁿ1ⁿ, 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ⁿ1ⁿ, 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ⁿ1ⁿ, 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₂on input x does the foll:

I ifx has the form 0ⁿ1ⁿ, 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₂on input x does the foll:

I ifx has the form 0ⁿ1ⁿ, 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₂on input x does the foll:

I ifx has the form 0ⁿ1ⁿ, 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₁ to instance ofP₂ I answer is yes forP₁ iff answer is yes forP₂

I then P₂ is at least as hard asP₁, i.e., I ifP₁is not decidable, neither isP₂ I ifP₁is not r.e., neither isP₂.

I note that every instance ofP₂ 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₁ to instance ofP₂ I answer is yes forP₁ iff answer is yes forP₂ I then P₂ is at least as hard asP₁, i.e.,

I ifP₁is not decidable, neither isP₂ I ifP₁is not r.e., neither isP₂.

I note that every instance ofP₂ 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₁ to instance ofP₂ I answer is yes forP₁ iff answer is yes forP₂ I then P₂ is at least as hard asP₁, i.e.,

I ifP₁is not decidable, neither isP₂

I ifP₁is not r.e., neither isP₂.

I note that every instance ofP₂ 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₁ to instance ofP₂ I answer is yes forP₁ iff answer is yes forP₂ I then P₂ is at least as hard asP₁, i.e.,

I ifP₁is not decidable, neither isP₂ I ifP₁is not r.e., neither isP₂.

I note that every instance ofP₂ 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₁ to instance ofP₂ I answer is yes forP₁ iff answer is yes forP₂ I then P₂ is at least as hard asP₁, i.e.,

I ifP₁is not decidable, neither isP₂ I ifP₁is not r.e., neither isP₂.

I note that every instance ofP₂ 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₁,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₁,M2i |M are TMs andL(M1) =L(M2)}.

Proof: Exercise.