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 Share Posted March 5 (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 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 account## Sign in

Already have an account? Sign in here.

Sign In Now