# Halting problem is undecidable proof confusion-:

• MHB
• shivajikobardan
In summary, the contradiction in this conversation is that the existence of a Turing machine H that solves the halting problem leads to the statement that "$D$ halts on $R(D)$" being both true and false, which is a contradiction. This is because if $D$ halts on $R(D)$, then $H'$ loops on $R(D)$, but if $D$ loops on $R(D)$, then $H'$ halts on $R(D)$. This results in the contradictory statement $P\leftrightarrow\neg P$, which is impossible.
shivajikobardan
https://slideplayer.com/slide/10708471/
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?

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?

I write $M(w)$ for the computation of a TM $M$ on inout $w$. The contradiction is as follows. If $D$ halts on $R(D)$, then by the definition of $H'$ we have $H'(R(D), R(D))$ loops. But the latter computation is a part of the computation $D(R(D))$; therefore, $D$ loops on $R(D)$. This is by itself is not a contradiction yet; it just means that $D$ cannot halt on $R(D)$. However, the inversion of that implication also holds: if $D$ loops on $R(D)$, then by the definition of $H'$ we have $H'(R(D), R(D))$ halts. Since this computation is the last portion of $D(R(D))$, the latter computation halts as well. So if we denote "$D$ halts on $R(D)$" by $P$, we get both $P\to\neg P$ (which implies $\neg P$) and $\neg P\to P$, which together with the former implication means $P\leftrightarrow \neg P$. This is a contradiction.

## FAQ: Halting problem is undecidable proof confusion-:

H2: What is the Halting Problem?

The Halting Problem is a fundamental problem in computer science that asks whether it is possible to create an algorithm that can determine whether a given program will halt (stop running) or continue to run infinitely. In other words, it is asking whether it is possible to predict the behavior of a program without actually running it.

H2: Why is the Halting Problem important?

The Halting Problem is important because it has far-reaching implications in computer science. It shows that there are limitations to what computers can do, and it also has practical applications in program verification and software testing.

H2: What does it mean for the Halting Problem to be undecidable?

Undecidability means that there is no algorithm or method that can solve a particular problem for all possible inputs. In the case of the Halting Problem, it means that there is no algorithm that can determine whether a given program will halt or run infinitely for all possible inputs.

H2: What is the proof of undecidability for the Halting Problem?

The proof of undecidability for the Halting Problem was first presented by Alan Turing in 1936. He showed that if there was an algorithm that could solve the Halting Problem, it would lead to a contradiction, known as the "halting problem paradox". This proved that the Halting Problem is undecidable.

H2: How does the Halting Problem relate to the concept of Turing completeness?

The Halting Problem is closely related to the concept of Turing completeness. A programming language or system is considered Turing complete if it can perform any computation that a Turing machine can. Since the Halting Problem is undecidable for Turing machines, it is also undecidable for any Turing-complete language or system.

Replies
4
Views
2K
Replies
2
Views
649
Replies
2
Views
1K
Replies
1
Views
880
Replies
54
Views
4K
Replies
29
Views
3K
Replies
6
Views
2K
Replies
9
Views
2K
Replies
1
Views
840
Replies
9
Views
2K