Are these two problems (1 and 2) equivalent in their description? 1) HALT TM = {

Question

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

1)          HALTTM = {

| 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 that I could see is that (2) does not cover the situation when it rejects. Whereas (1) covers the both i.e. accept & halt AND reject & halt.

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?

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 turin 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.