Question

Given a Turing machine M on alphabet {m,e,b,r} we're asked to determine if member $\in$ L(M). You must realize that M is not one specific machine and can be any turing Machine with the same alphabet. My goal is to determine whenever this problem is decidable or not.

My idea was to use mapping reducibility. The goal was to see if we can translate all problems from $A_{TM}$ which is known to be undecidable into our current problem. This would make our current problem undecidable by contagion. However I'm struggling in doing so because I'm not sure if it's possible. $A_{TM}$ is defined as a Turing machine M that accepts the word w.

Any help to get unstuck would be appreciated.

Was it helpful?

Solution

I would try it like this:

Reduction from $A_{TM}$: Given TM $A$ und word $w$.

Use that to define a new machine $A'$ that works as follows:

  1. Run like $A$ on input $w$
  2. If $A$ rejects $w$, go into eternal loop.
  3. If $A$ accepts, delete the band content and write "member"
Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top