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?

 

 

 

 

 

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, 20223 yr by SuperSlim