Timeline for How to formalize "Is there a proof for every instance of the halting problem?"?
Current License: CC BY-SA 3.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 14, 2014 at 19:33 | comment | added | Joel David Hamkins | @მამუკაჯიბლაძე No, my answer at the other question (mathoverflow.net/a/186498/1946) shows that for any give $p$, there is a c.e. sound theory $T_p$ that correctly settles whether $p$ halts or not. This answer here shows that we cannot computably go from $p$ to that theory $T_p$. But meanwhile, the noncomputable consistent sound theory TA always works. | |
| Nov 14, 2014 at 19:01 | comment | added | მამუკა ჯიბლაძე | Does this rule out that for each given $p$ there is a $T_p$ which can be described effectively in some rigorous sense? If I am not mistaken, $TA$ cannot be effectively described in any sense... | |
| Nov 10, 2014 at 11:09 | comment | added | Ward Blondé | Thanks! The answer on my question is 'no' (for clarity) and I am certainly not unsatisfied with this. Instead, I was unsatisfied with the most popular answer of Terry Tao here, which makes use of exotic numbers, as well as some comments there that refute the doubt of Knuth. This made me have the impression that mathematicians have a way to bypass the negative results of Gödel and the halting problem. | |
| Nov 9, 2014 at 21:53 | history | edited | Joel David Hamkins | CC BY-SA 3.0 |
added 98 characters in body
|
| Nov 9, 2014 at 19:24 | history | answered | Joel David Hamkins | CC BY-SA 3.0 |