Halting problem is undecidable proof confusion-:

  • #1
shivajikobardan
674
54
https://slideplayer.com/slide/10708471/
This is the context I am talking about.

KgCMu.png


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?

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?
 
Technology news on Phys.org
  • #2
I write for the computation of a TM on inout . The contradiction is as follows. If halts on , then by the definition of we have loops. But the latter computation is a part of the computation ; therefore, loops on . This is by itself is not a contradiction yet; it just means that cannot halt on . However, the inversion of that implication also holds: if loops on , then by the definition of we have halts. Since this computation is the last portion of , the latter computation halts as well. So if we denote " halts on " by , we get both (which implies ) and , which together with the former implication means . This is a contradiction.
 

Similar threads

Replies
4
Views
2K
Replies
2
Views
748
Replies
2
Views
1K
Replies
1
Views
987
Replies
6
Views
2K
Replies
9
Views
2K
Replies
1
Views
932
Replies
9
Views
2K
Back
Top