CODEWITHSUNDEEP
theoryturing-machinescomputation
Jerome Morrow
Jerome Morrow

Reputation: 21

M is a Turing machine that accepts string w and does not accept string ε

I need to prove whether this language is recognizable or not:

{ ⟨M, w⟩: M is a Turing machine that accepts string w and does not accept string ε }

I figure I could do a reduction on ATM, but how do I handle the empty string?

Upvotes: 2

Views: 2404

Answers (1)

templatetypedef
templatetypedef

Reputation: 373042

Here's one way to do a reduction from the complement of ATM to your language.

Given a TM M and a string w, build this TM/string pair:

M' = "On input x:
         If x = "iheartquokkas", accept.
         Otherwise:
            Run M on w.
            If M accepts, accept;
            If M rejects, reject;
            (Implicitly: if M loops, loop.)"
w' = "iheartquokkas"

First, suppose that M does not accept w. Then machine M' does indeed accept the string w', because it's programmed to do so. Additionally, when you run M' on ε, it will run M on w and never accept because M doesn't accept w. Thus M' accepts w' but not ε, so ⟨M', w'⟩ is in your language.

Second, suppose that M accepts w. Then when you run M' on ε, it will accept, so it is not the case that M' accepts w' but not ε. Therefore, ⟨M', w'⟩ is not in your language.

You now have a mapping reduction from ATM's complement to your language, so your language isn't recognizable.

Now, can you prove that it's not co-recognizable?

Upvotes: 0

Related Questions