Are these two problems (1 and 2) partially equivalent in their description? 1) -

Question

Are these two problems (1 and 2) partially equivalent in their description?

1)          -HALTTM = {<P>

| P is a TM and P halts on input }. Show that -HALTTM is undecidable

2)          ATM = { | M is a TM that accepts }. Show that ATM is undecidable.

The only difference between these two that I could see is that (2) does not cover the situation when it rejects and halts (i.e. it covers the accepts and halts) whereas (1) covers the both i.e. accepts & halts AND rejects & halts.

What could be a solution for (1)? Do we have to resolve it by Turing reduction or mapping reduction? Do we have to resolve it by reducing

ATM or HALTTM

to
-HALTTM

Or there is some other possible way ? Please outline.

Explanation / Answer

For the give situation in both statemet of turing machine both description are not equivalent because the first statement HALTTM turing-recognizable .The universal Turing machine MU of Theorem E is easy to convert into a TM that simulates the computation of M on input w and accepts if and only if the computation being simulated halts.So it can be resolve by turing reduction ATM to HALTTM

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

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