shivajikobardan Posted November 16, 2021 Share Posted November 16, 2021 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 More sharing options...
SuperSlim Posted March 5, 2022 Share Posted March 5, 2022 (edited) 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 March 5, 2022 by SuperSlim Link to comment Share on other sites More sharing options...
Recommended Posts
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 accountSign in
Already have an account? Sign in here.
Sign In Now