Proof That Computers Can't Do Everything (The Halting Problem)

What people said

Strong rec Polygnome · 2018-07 · Computer Science Stack Exchange · on “Halting Problem without self-reference: why does this argument not suffice (or does it)?”

Are you aware of this video [this video] ? Its the most intuitive explanation of the halting problem I've ever seen.

Strong rec Andrej Bauer · 2024-03 · Computer Science Stack Exchange · on “What is the role of diagonalization in the proof of undecidability of the halting problem?”

Yes, the proof you pointed to is refutation by contradiction (it explicitly says "proof by contradiction" and proceeds to refute the claim by assuming it). It is a proof by diagonalization, specifically at one point is says "how about $\mathrm{OPP}(\mathrm{OPP})$?". This sort of self-application is a telltale sign that diagonalization is occuring. (P.S. I do not recommend this proof. There are classic textbooks that do a much better job, but nothing beats this video [this video] , which is also refutation by contradiction using diagonalization.)

Recommends Henry akpo · 2015-11 · Computer Science Stack Exchange · on “Is the halting problem a matter of an encoding scheme ?”

I was reading about the halting problem recently, there is a video [this video] on youtube where it tries to explain the halting problem easily (since it is complicated to explain). So, (A,C & H) have different inputs, if we suppose that we can run the three inputs on a machine (x) using one encoding scheme (i.e encoding for chess = arthemtic), would that solve the halting problem ? Is it a problem of encoding different forms of inputs to the machine itself, or is it a problem of always getting the right answer to the input ?

Recommends Andrej Bauer · 2016-11 · Computer Science Stack Exchange · on “Proof of the undecidability of the Halting Problem”

Try a prettier proof [this video] with animations. And since ansewrs should contain more than just a link to a site, here's the answer to your question. First, let us recall how the proof of non-existence of the Halting oracle works. We prove that given any candidate H for a Halting oracle, there is a program P and an input a for which H fails to predict correctly what P(a) does. Theorem: Let H be any program which takes two inputs and always returns either halt or loop . Then there exists a program Q and an input a such that Q(a) halts if, and only if, H(Q,a) returns loop . Proof. Consider the program program P(y): if H(y,y) = halt then loop forever else: return Let Q = P and a = P . Either H(Q,

Recommends D.W. · 2018-07 · Computer Science Stack Exchange · on “Halting Problem without self-reference: why does this argument not suffice (or does it)?”

I don't think this is a good way to present the halting problem, because it sweeps a critical issue under the covers in a sneaky way. I suggest sticking with a more standard presentation, such as the one you linked. If you want to find a way to explain it in a way that minimizes the technical content, the presentation in this video [this video] is surprisingly accessible, and remains true to the logic of the standard proof. On to the difficulties with your proposal. In your proposal, it's not trivial to write down the code for such a Q . Think about what it means to have the line if H(Q,J) then loop forever Recall that the first argument to H is a bit-string that contains the code / algorithm / T