4 ms·
> We should just solve the halting problem That might be a little bit like "draw the rest of the damn owl" and besides, wouldn't that destroy our encryption sc
by ndsipa_pomu 3y ago
> We should just solve the halting problem
That might be a little bit like "draw the rest of the damn owl" and besides, wouldn't that destroy our encryption schemes?
- explaininjs 3y agoIt’s a joke, it’s mathematically unsolvable. Though even if it were I don’t see the connection to encryption?
- ndsipa_pomu 3y agoSorry if I got wooshed. It's currently unsolved, but I don't think that it's been proved to be unsolvable as surely that would prove P ≠ NP. The connection to encryption is that integer factorisation could then be solved in polynomial time which would break current systems, though in theory a much longer key length could be used to try to outpace computer power, especially if the polynomial algorithm is hugely inefficient. Edit: I see that the halting problem has indeed been proved to be unsolvable and it doesn't imply P ≠ NP
- explaininjs 3y agoP/NP and Halting are entirely different concepts. I suggest reading up on the Halting problem - it’s actually very mind opening. Edit: it wouldn’t be a stretch to call it the most important result in all of mathematics
- ndsipa_pomu 3y agoIf you have a solution to the halting problem, then it would be possible to cast the P/NP problems in terms of a program and knowing whether or not it halts would allow you to determine whether P=NP.
- explaininjs 3y agoThat may be, but statements that start “if false …” aren’t very useful.
- sharkbot 3y agoThe halting problem has been proven definitively undecidable via proof by contradiction, by Alan Turing. The proof implicitly created the notion of Turing machines, a key model of computation. There is a solution to the halting problem. It’s that it is undecidable.
- dreamcompiler 3y agoYes. The Halting Problem is just Gõdel incompleteness in drag. They're both the same idea and they're both thoroughly proven.
- explaininjs 3y agoI had originally written something to that effect, but recanted after I saw Turing claimed “what I shall prove is quite different from the well-known results of Gödel”. I’d need to sit down longer to determine how equivalent they really are.
- dreamcompiler 3y agoWould love to see the reference for this. I expect he might be referring to the idea of executing an embodied algorithm on a machine, while Gödel was talking about pure math.
- explaininjs 3y agoPage 27 here: https://www.cs.ox.ac.uk/activities/ieg/e-library/sources/tp2-ie.pdf https://www.cs.ox.ac.uk/activities/ieg/e-library/sources/tp2...
- tsimionescu 3y agoThe halting problem (writing an algorithm which can take any other algorithm and an initial condition and return true/false for whether it halts or not) has nothing to do with P or NP. Even if all algorithms were solvable in O(n), the halting problem would still be unsolvable.
- bregma 3y agoIt's humour because the "halting problem" has a simple and elegant proof that it is impossible to solve in the general case. TFA's request for general computing to use unlimited stack operation for every thread of execution is equivalent to a call for the halting problem to be provably possible in O(1) time. It's the unexpected juxtaposition of these two oppositional ideas that provides the basis for humour. Of course, if it has to be explained it loses its funny.