[PDF] Homework 10 Solutions However ETM is Turing-recognizable (

View - Download Homework 10 Solutions

Previous PDF

Next PDF

CS 341: Foundations of Computer Science II

Prof. Marvin Nakayama

Homework 10 Solutions

1. If AmBandBis a regular language, does that imply thatAis a regular language? Answer:No. For example, dene the languagesA=f0n1njn0gandB=f1g, both over the alphabet =f0;1g. Dene the functionf: !as f(w) =n1ifw2A;

0ifw62A:

Observe thatAis a context-free language, so it is also Turing-decidable. Thus,fis a computable function. Also,w2Aif and only iff(w) = 1, which is true if and only iff(w)2B. Hence,AmB. LanguageAis nonregular, butBis regular since it is nite. 2. Sho wthat ATMis not mapping reducible toETM. In other words, show that no computable function reducesATMtoETM. (Hint: Use a proof by contradiction, and facts you already know aboutATMandETM.) Answer:Suppose for a contradiction thatATMmETMvia reductionf. This means thatw2ATMif and only iff(w)2ETM, which is equivalent to sayingw62ATM if and only iff(w)62ETM. Therefore, using the same reduction functionf, we have thatA TMmE

TM. However,E

TMis Turing-recognizable (HW 8, problem 4) andA

TMis not Turing-recognizable (Corollary 4.23), contradicting Theorem 5.22. 3.

Con siderthe language

A"

TM=fhMi jMis a TM that accepts"g:

Show thatA"TMis undecidable.

Answer:We will show thatATMreduces toA"TM. Suppose for contradiction that A" TMis decidable, and letRbe a TM that decidesA"TM. We construct another TM Swith inputhM;withat does the following. It rst usesMandwto construct a new TMM2, which takes inputx. Ifx6=", thenM2accepts; otherwise,M2runsM on inputwandM2accepts ifMacceptsw. Note thatM2recognizes the language f"gifMdoes not acceptw; otherwise,M2recognizes the language. In other words,M2accepts"if and only ifMacceptsw. So our TMSdecidesATM, which is a contradiction since we knowATMis undecidable. 1

Here are the details of our TMS:

S=\On inputhM;wi, whereMis a TM andwis a string:

0.Check ifhM;wiis a valid encoding of a TMMand stringw.

If not,reject.

1.Construct the following TMM2fromMandw:

M

2=\On inputx:

1.Ifx6=",accept.

2.Ifx=", then runMon inputw

andacceptifMacceptsw."

2.RunRon inputhM2i.

3.IfRaccepts,accept; ifRrejects,reject."

4. A useless statein a Turing machine is one that is never entered on any input string. Consider the problem of determining whether a state in a Turing machine is useless. Formulate this problem as a language and show it is undecidable. Answer:We dene the decision problem with the language

USELESS

TM=fhM;qijqis a useless state in TMMg:

We show thatUSELESSTMis undecidable by reducingETMtoUSELESSTM, where E TM=fhMijMis a TM andL(M) =;g. We knowETMis undecidable by The- orem 5.2. Suppose thatUSELESSTMis decidable and that TMRdecides it. Note that for any Turing machineMwith accept stateqaccept,qacceptis useless if and only ifL(M) =;. Thus, because TMRsolvesUSELESSTM, we can useRto check ifqacceptis a useless state to decideETM. Specically, below is a TMSthat decidesETMby using the deciderRforUSELESSTMas a subroutine:

S=\On inputhMi, whereMis a TM:

1.Run TMRon inputhM;qaccepti, whereqacceptis

the accept state ofM.

2.IfRaccepts,accept. IfRrejects,reject."

However, because we knownETMis undecidable, there cannot exist a TM that decides

USELESS

TM. 2quotesdbs_dbs14.pdfusesText_20

[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