[PDF] [PDF] 1 Reducability HALTTM = {?Mw? M is a

View - Download [PDF] 1 Reducability

Previous PDF

Next PDF

CSCC63 Worksheet { Reducability

For your reference,ATMis dened to be the languagefhM;wi jMacceptswg.

1 ReducabilityTheorem 5.1

HALT TM=fhM;wi jMis aTMthat halts on inputwgis undecidable.Proof. Assume thatTM RdecidesHALTTMand we will constructTM Sto decide the acceptance prob- lem.

S= \On inputhM;wi,

1.

Run TM Ron inputhM;wi

2.

If Rrejects,reject.

3.

If Raccepts, simulateMonwuntil it halts.

4. If Mhas accepted,accept; ifMhas rejected,reject.Theorem 5.2 E TM=fhMi jMis a TM such thatL(M) =fggis undecidable.Proof Idea.

LetRbe a TM that decidesETM.

ConstructSthat decidesATMusingR.

Construct anotherTM M1which behaves likeMon inputw, but rejects all other inputs. PassM1toR. IfL(M1) is empty, thenRaccepts (i.e.,M1does not acceptw.) IfM1acceptsw, thenL(M1)6=fg, soRrejects andSaccepts. 1 Proof.AssumeRdecidesETM, and constructSas follows:

S= \On inputhM;wi:

1.

Construct hM1i, fromMandw:

M

1= \On inputx:

Ifx6=w,reject;

Else accept ifMacceptsw."

2. Run Ron inputhM1iand do the opposite (ifRaccepts, reject; ifRrejects, accept)."

Hence,SdecidesATM, a contradiction!Theorem 5.4

EQ TM=fhM1;M2ijM1andM2areTMs such thatL(M1) =L(M2)gis undecidable.Proof Idea. Q.Which undecidable language should we use to show thatEQTMis undecidable? E TM

Q.How does the reduction work?

ReduceETMtoEQTM

ConstructME, a TM that doesn't accept anything.

To determine ifL(M) is empty, passMandMEtoEQTM

Proof.

AssumeRdecidesEQTMand constructSto decideETM.

S= \On inputhMi:

1.

Compute hMEi, the description of the followingTM:

2.ME= \On inputx: reject."

3.

Run Ron inputhM;M0i.

4.

If Raccepts,accept, ifRrejects,reject."

ThenSdecidesETM, contradiction.

2

Theorem 5.3

REGULAR

TM=fhMi jMis aTMsuch thatL(M)is regulargis undecidable.Exercise: Try this one (useATMas the other language). The solution is in the textbook and

we'll discuss in tutorial.

2 Mapping Reducibility and Formalizing Reduction Proofs

General structure ofproof of undecidabilityof some languageA:

AssumeRdecidesA.

S= \On inputx:

Computeysuch thaty2A()x2B.

RunRonyandacceptifRaccepts andrejectifRrejects."

Then,SdecidesBbecausey2A()x2B.

Since the structure is always the same, concentrate on \core" part: construction ofyfromxsuch thaty2A()x2B.Denition 5.20Mapping Reducibility (a.k.a reduction).

LanguageAismapping reducibleto languageB, written

AmB if there is acomputable functionf:!, where for everyw, w2A,f(w)2B: The functionfis called thereductionofAtoB.Example 5.26.ETMmEQTM.

GivenhMi, constructhM1;M2ias follows:

M1=M,

M2= a xedTMthat rejects all inputs

This is computable (copy string, append constant string). 3

SinceL(M1) =L(M) andL(M2) =fg

hMi 2ETM()L(M) =fg ()L(M1) =L(M2) () hM1;M2i 2EQTM:Theorem 5.22

IfAmBandBis decidable, thenAis decidable.

Theorem 5.28

IfAmBandBis recognizable, thenAis recognizable.Corollary 5.23

IfAmBandAis undecidable, thenBis undecidable.

Corollary 5.29:

IfAmBandAis unrecognizable, thenBis unrecognizable.Properties.

AmB()ACmBC

Q.Why?

(Straight from denition, since statement \w2A()f(w)2B" is equivalent to \w62A() f(w)62B" and \w62A" = \w2AC".)

IfAmBandBmC;thenAmC.

Q.Why?

(Easy exercise, based on function composition: if f,g computable, then g(f()) computable.)

3 Let's Practice.

We showed thatETMis undecidable by showing a reduction fromATMtoETM. The proof was: Proof.AssumeRdecidesETM, and constructSas follows:

S= \On inputhM;wi:

1.

Construct hM1i, fromMandw:

M

1= \On inputx:

4

Ifx6=w,reject;

Else accept ifMacceptsw."

2. Run Ron inputhM1iand do the opposite (ifRaccepts, reject; ifRrejects, accept)."

Hence,SdecidesATM, a contradiction!

This is actually a proof thatATMmECTM.Why??.

In fact one can prove thatATM6mETM. (done in tutorial)

3.1 Prove thatHALTTMisundecidable.

Q.What is thereduction?

A

TMmHALTTM

GivenhM;wi, constructhM0;w0isuch that

Macceptsw()M0halts onw0

or equivalently (hM;wiinATM)()(hM0;w0iinHALTTM) . Dene M0=Mexcept replace all transitions toqrejectwith transition to stateqnew, then add transitions fromqnewtoqnewfor each input symbol (qnewis deliberate innite loop) w' =w

Explanation.

IfMacceptsw, thenM0acceptsw0;

ifMrejectsw, thenM0loops onw0; ifMloops onw, thenM0loops onw0, i.e.,Macceptsw()M0halts onw0, as desired. 5

4 Mapping Reducibility Examples cont'd

A TMmREGULARTM:Goal.GivenhM;wi, constructhM0isuch that

Macceptsw()L(M0) is regular

of equivalently (hM;wiinATM)()(hM0iinREGULARTM) M

0= \On input x:

1.

Accept if x= 0n1nfor somen0.

2.

Else, run Monwand do the same."

Explanation.

IfMacceptsw, thenM0accepts everything, i.e.,L(M0) = isregular; ifMdoes not acceptw, thenM0accepts only 0n1n, i.e.,L(M0) =f0n1n:n0gis not regular.

5 Examples cont...EQ

TMis neitherrecognizablenorco-recognizable.Recall a language isco-recognizableif its complement is recognizable.

Similar denition for decidability unnecessary { do you see why? Q.What is thereductionto show thatEQTMis notco-recognizable? A

TMmEQTM

Q.Why does this work?

Because it is equiv. toAcTMmEQcTMandAcTMis not recognizable.

On inputhM;wi, constructhM1;M2ias follows:

1.M1= \On inputx: runMonw(ignorex) and do the same."

2.M2= \On inputx: accept."

6

ExplanationThen,

hM;wi 2ATM()Macceptsw ()M1accepts every string ()L(M1) =L(M2) () hM1;M2i 2EQTM:

This proves thatEQTMis notco-recognizable.

Q.How can we show thatEQTMisnot recognizable?

ShowATMmEQcTM(equiv. toAcTMmEQTM):

On inputhM;wi, constructhM1;M2ias follows:

1.M1= \On inputx: runMonw(ignorex) and do the same."

2.M2= \On inputx: reject."

ExplanationThen,

hM;wi 2ATM()Macceptsw ()M1accepts every string ()L(M1)6=L(M2) () hM1;M2i 62EQTM () hM1;M2i 2EQcTM:

This proves thatEQTMisnot recognizable.

6 Examples cont...INF=fhMi:L(M) contains innitely many stringsgis neitherrecognizablenorco-recognizable.Q.What should thereductionbe to proveINFis notco-recognizable?

HALT

TMmINF

Q.Why?

SinceHALTTMis not decidable, but is recognizable (easy to report ifMhalts onw), it must be thatHALTCTMisnotrecognizable. 7

On inputhM;wi, constructhM0ias follows:

M'= \On inputx:

1.

Run Monw.

2.

Accept if Mhalts."

Explanation

IfMhaltsonw, thenM0accepts all strings soL(M')isinnite. IfMloopsonw, thenM0accepts no string soL(M0) isnite.

This showsINFcisunrecognizable.

Q.How can we show thatINFis notrecognizable?

We can show thatHALTTMmINFc.

On inputhM;wi, constructhM0ias follows:

M

0= \On inputx:

1.

Run Monwforjxjsteps.

2.

Accept if Mhas not halted."

Explanation

IfMhalts onw, thenM0accepts only the strings up to a certain length, soL(M0) is nite. IfMloops onw, thenM0accepts all strings soL(M0) is innite.

This showsINFisunrecognizable.

8quotesdbs_dbs9.pdfusesText_15

[PDF] is expedia good for car rentals

[PDF] is fog a colloid

[PDF] is form 8332 necessary

[PDF] is france constitution written or unwritten

[PDF] is full fat milk homogeneous or heterogeneous

[PDF] is glucose a crystalloid

[PDF] is green a primary color

[PDF] is hamburg a rich city

[PDF] is hand sanitizer dangerous goods

[PDF] is handset leasing profitable for telecom companies

[PDF] is high alkalinity in drinking water bad

[PDF] is interest income taxable in singapore

[PDF] is iphone packaging recyclable

[PDF] is iron a pure substance

[PDF] is iron filings a mixture