4 ms·
Yes. The Halting Problem is just Gõdel incompleteness in drag. They're both the same idea and they're both thoroughly proven.
by dreamcompiler 3y ago
Yes. 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...