ETM = {〈M〉 M is a TM such that L(M) = {}} is undecidable Let R be a TM that decides ETM If A ≤m B and B is recognizable, then A is recognizable
Previous PDF | Next PDF |
[PDF] Homework 10 Solutions
However, ETM is Turing-recognizable (HW 8, problem 4) and ATM is not Turing- recognizable (Corollary 4 23), contradicting Theorem 5 22 3 Consider the
[PDF] Homework 8 Solutions
Consider the emptiness problem for Turing machines: ETM = { 〈M〉 M is a Turing machine with L(M) = ∅} Show that ETM is co-Turing-recognizable (A
[PDF] Tutorial 5
If both L and L are recognizable then L is decidable As we know that ATM , HALTTM , ETM are recognizable, their complements cannot be rec- ognizable,
[PDF] 10 Reducibility
HALTTM is Turing-recognizable since it can be recognized by TM U ETM = {< M > M is a TM and L(M) = /0} is undecidable Proof: Reduce ATM to ETM
[PDF] and let f be the function that maps 0 1 to 1 and maps all other s
But, ¬ETM is Turing recognizable and ¬ATM is not, which contradicts Theorem 5 22 This is a contradiction Therefore, ATM is not mapping reducible to ETM 5 7 A
[PDF] 1 Reducability
ETM = {〈M〉 M is a TM such that L(M) = {}} is undecidable Let R be a TM that decides ETM If A ≤m B and B is recognizable, then A is recognizable
[PDF] CSE 105 - UCSD CSE
ETM = { M is TM, L(M) is empty} A Decidable B Undecidable, recognizable, with recognizable complement C Undecidable, recognizable, with
[PDF] ECS120 Discussion Notes
28 nov 2006 · The emptiness problem, ETM = {(M )M is a TM and L(M) = ∅}, is undecidable How to prove a language is Turing-recognizable or
[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
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:
M1= \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 TMQ.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.
2Theorem 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). 3SinceL(M1) =L(M) andL(M2) =fg
hMi 2ETM()L(M) =fg ()L(M1) =L(M2) () hM1;M2i 2EQTM:Theorem 5.22IfAmBandBis decidable, thenAis decidable.
Theorem 5.28
IfAmBandBis recognizable, thenAis recognizable.Corollary 5.23IfAmBandAis 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:
M1= \On inputx:
4Ifx6=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?
ATMmHALTTM
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' =wExplanation.
IfMacceptsw, thenM0acceptsw0;
ifMrejectsw, thenM0loops onw0; ifMloops onw, thenM0loops onw0, i.e.,Macceptsw()M0halts onw0, as desired. 54 Mapping Reducibility Examples cont'd
A TMmREGULARTM:Goal.GivenhM;wi, constructhM0isuch thatMacceptsw()L(M0) is regular
of equivalently (hM;wiinATM)()(hM0iinREGULARTM) M0= \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