Describe logic why it is not enough to show reduction

Assignment Help Programming Languages

Reference no: EM1367216

1) We know by rice's theorem that none of the following problems are decidable.However,are they recursively enumerable,or non-RE?
a) IS L(M) infinite?

2) If we can only show: if x belongs to A, then y does not belongs to B;explain the logic why it is not enough to show A reduction B.IN other words why the theory needs to prove"if and only if"?

3) Show that the halting problem,the set of (M,w) pairs such that M halts(with or without accepting) when given input w is RE but not recursive.

Reference no: EM1367216

Questions Cloud

Change in exchange rates : In September 2003, a United State retailer wants to buy canola oil from a Canadian farm. At that time in Canada, one barrel of canola oil value C$2.

What is the amplitude of oscillation : A damped mass-spring system oscillates at 280 Hz. The time constant of the system is 2.0 s. At t = 0, the amplitude of oscillation is 8.4 cm and the energy of the oscillating system is then 84 J.

Demand curves and airline pricing : Suppose an airline flying on the Charolette-Chicago route has estimated the demand curves for three different types of customers: business (no advance purchase), leisure (7 day advance purchase), and discount (14 day advance purchase) travellers. ..

Territoriality of communities-division and conflict : Territoriality of communities within communities often creates division and conflict.

Describe logic why it is not enough to show reduction : If we can only show: if x belongs to A, then y does not belongs to B;explain the logic why it is not enough to show A reduction B.IN other words why the theory needs to prove"if and only if"?

Impact of community health issue : Caused by a parasite that lives in sand flies, lesions appear on the skin which can impact a person with swelling and sores that can last for months. What impact can you think of regarding this community health issue?

Determining pricing problem : Assume a manager of a profitable department store you're confronted with the pricing problem. You've two types of customers

Determine the effect on currency : Venezuela had considerable capital outflows after election of Hugo Chavez. If Venezuela had fixed exchange rates, determine what effect would these flows have had on Venezuela's overall balance and value of the Bolivar

Estimate amount of former foreign-monopoly profit : Estimate amount of former foreign-monopoly profit that is transferred as tariff revenue to home nation when home nation imposes tariff.

User Account

All Pages