1
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ A small warning: If you frequently delete questions when they are downvoted or commented on (e.g., maybe you are deleting the question, revising it, and re-asking the improved/revised version as a new question), you might risk running into a question ban. In those circumstances it might be better to revise the question to improve it and address the feedback, rather than deleting it. I don't fully understand the mechanics behind the question ban or what exactly can trigger it, but I believe that self-deleted downvoted questions can contribute, so I wanted to let you know in advance. $\endgroup$
    – D.W.
    Aug 6, 2020 at 18:32

1 Answer 1

1
$\begingroup$

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"
$\endgroup$
1
  • $\begingroup$ thank you for the answer! $\endgroup$
    – WindBreeze
    Aug 6, 2020 at 17:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.