See below for a mapping reduction M# from H to L = { : L(M) contains a string en

Question

See below for a mapping reduction M# from H to L = { : L(M) contains a string ending in b}. It could be part of proof that L D. Let = {a, b}. Imagine there is a TM called Oracle that could decide L. As examples, Oracle would reject Ø, but accept L = { w : w = b*a*b}.

M# definition:

1. Erase any input.

2. Write w on the tape.

3. Run M on w.

4. Accept

i. Write a characteristic function for L(M#) if H. Why or why not would Oracle accept L(M#) in this case?

ii. Write a characteristic function for L(M#) if H. Why or why not would Oracle accept L(M#) in this case?

Explanation / Answer

As we know by definition mapping reduction is a technique to find any problem decidable or undecidable by reducing it to another problem.

mapping reduction M# from H to L = { : L(M) contains a string ending in b}

it could be {b},{bab}*

For example we can consider, Oracle would reject Ø, but accept L = { w : w = b*a*b}

1. Here L(M#) if belongs to( ) H

characteristic function:

If <M,w> LTM    then L(M' ) = { },<M'> L

In this case Oracle accept L(M#) . because H is mapping reducible to L and L(M#) if H. That means L is decidable, then H must be decidable.

2. Here L(M#) if not belongs to( ) H

characteristic function:

f <M,w> LTM    then L(M' ) =  *,<M'> L

A language is decidable if and only if its characteristic function XL is computable function XL : * *

In this case Oracle not accept L(M#) .

Oracle accepts everything or nothing, depending on whether M halts on w while writing on the tape.

That means it is clear this is not decidable.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.