Jump to content

Halting problem is undecidable proof confusion-:


Recommended Posts

THE HALTING PROBLEM - PROOF. Review  What makes a problem decidable?  3 properties of an efficient algorithm?  What is the meaning of “complete”, “mechanistic”, -  ppt download

This is the context I am talking about.




What contradiction occur here? We begin by telling that there is a Turing machine H that solves the halting problem. So how does this contradicts? Can you tell me about that?






Link to comment
Share on other sites

  • 3 months later...

The halting problem is sort of recursive. It says that given a Turing machine T, there is no Turing machine T' which can decide if the first Turing machine will halt. Generally, you assume there is a Turing machine, H, that can decide if T will halt and then show this leads to a contradiction.

So you prove it by using proof by contradiction.

Edited by SuperSlim
Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.