5

Possible Duplicate:
Are there any proofs the undecidability of the halting problem that does not depend on self-referencing or diagonalization ?

As is stated, can every undecidability proof can be stated in form of diagonalization?

Also, can halting problem be reduced to every undecidable problem? (we all know that every undecidable problem can be reduced to halting problem)

Thanks.

Community
  • 1
  • 8
    For your second question, have a look at http://en.wikipedia.org/wiki/Turing_degree: it answers your question in the negative. To get a good answer for your first question, I think you'll have to define 'diagonalization' more rigorously. – Alex ten Brink Jan 22 '12 at 23:13
  • 2
    Welcome to cstheory, a Q&A site for research-level questions in theoretical computer science (TCS). Your question does not appear to be a research-level question in TCS. Please see the [FAQ] for more information on what is meant by this and suggestions for sites that might welcome your question. Finally, if your question is closed for being out of scope, and you believe you can edit the question to make it a research-level question, please feel free to do so. Closing is not permanent and questions can be reopened, check the [FAQ] for more information. – Kaveh Jan 22 '12 at 23:48
  • @Kaveh: Why did you delete the comment in which you proposed to close this question as an exact duplicate of 2853? I had voted to do so because I agreed to your explanation. Without the explanation, it can be hard to understand why this has been closed this way. – Tsuyoshi Ito Jan 23 '12 at 15:16
  • @Tsuyoshi, I didn't. The SE has changed the system, it seems to automatically delete the comments that links to the duplicate. – Kaveh Jan 23 '12 at 20:34
  • @Kaveh: Ugh. Silly misfeature…. – Tsuyoshi Ito Jan 24 '12 at 01:04

0 Answers0