See below for a mapping reduction M# from H to L = { : L(M) contains a string en
ID: 3866296 • Letter: S
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.