Timeline for Is there any concrete relation between Gödel's incompleteness theorem, the halting problem and universal Turing machines?
Current License: CC BY-SA 3.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 27, 2020 at 13:10 | answer | added | Julius Kunze | timeline score: 3 | |
| Jul 19, 2018 at 14:12 | comment | added | micans | Somewhat related ... I always misremember Hofstadter's parabel where the Tortoise keeps breaking Achilles' record player, as applying to the halting problem. In fact, I found this thread by (re)searching my confusion. I still feel the parabel translates more naturally and directly to the halting problem, but this is without any deep understanding of either theorem. | |
| Mar 5, 2018 at 12:12 | history | edited | Raphael |
edited tags
|
|
| Apr 13, 2017 at 12:19 | history | edited | CommunityBot |
replaced http://math.stackexchange.com/ with https://math.stackexchange.com/
|
|
| Oct 10, 2016 at 11:12 | answer | added | stoopkid | timeline score: 0 | |
| Jul 13, 2014 at 7:45 | history | edited | Marc van Leeuwen | CC BY-SA 3.0 |
typos
|
| Oct 11, 2012 at 16:19 | comment | added | vzn | yes indeed the two proofs are conceptually extremely similar and in fact one way to look at it is that Godel constructed a sort of turing-complete logic in arithmetic. there are many books that point out this conceptual equivalence. eg Godel Escher Bach by hofstadter or Emperors New Mind by penrose.... | |
| Apr 13, 2012 at 6:54 | history | tweeted | twitter.com/#!/StackCompSci/status/190694384835112961 | ||
| Mar 24, 2012 at 15:53 | vote | accept | Marc van Leeuwen | ||
| Mar 21, 2012 at 6:56 | answer | added | Marcos Villagra | timeline score: 38 | |
| Mar 17, 2012 at 18:04 | comment | added | Marc van Leeuwen | @Raphael: I am very well aware that there is a large conceptual difference between the statements of incompleteness theorem and of the undecidability of the halting problem. However the negative form of incompleteness: a sufficiently powerful formal system cannot be both consistent and complete, does translate into an indecidability statement: since the set of theorems deducible in a formal system is semi-decidable by construction, completeness would make the set of non-theorems semi-decidable as well (as negations of theorems, assuming consistency, or else as the empty set), hence decidable. | |
| Mar 17, 2012 at 15:45 | answer | added | Dai | timeline score: 17 | |
| Mar 15, 2012 at 18:10 | comment | added | Raphael | You have one conceptual problem: algorithmic decidability (Halting problem) and derivability resp. provability (logics) are two very different concepts; you seem to use "decidability" for both. | |
| Mar 15, 2012 at 18:06 | answer | added | jmad | timeline score: 6 | |
| Mar 15, 2012 at 16:51 | answer | added | Suresh | timeline score: 21 | |
| Mar 15, 2012 at 16:43 | history | asked | Marc van Leeuwen | CC BY-SA 3.0 |