Timeline for Variant of the usual proof method for undecidability of the halting problem
Current License: CC BY-SA 3.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 19, 2011 at 19:38 | comment | added | Steve Huntsman | I think I see why the approach I was looking for doesn't seem to be taken often. The diagonal argument would require constructing a special TM that "does the opposite" on the halting problem. If we're talking about partial recursive functions this is very simple, and in fact I found a reference that tackles it this way. But if we're trying to be concrete about TMs this construction seems to require more abstraction than dividing tapes into programs and inputs. | |
| Sep 19, 2011 at 16:47 | comment | added | Steve Huntsman | I am seeing lots of "well you can do it another way instead...". These approaches are all too abstract. The students are not familiar with programming. I am trying an experiment here to see if I can successfully introduce TMs to students that otherwise would never see something like this. I am committed to using an array (and so enumerating either TMs or programs) because I am covering the uncountability of the reals in the same material, and this lets me use the same diagonal hammer twice. Actually, when proving a weak form of Gödel incompleteness it lets me use the same hammer thrice. | |
| Sep 19, 2011 at 15:09 | answer | added | Brendan McKay | timeline score: 7 | |
| Sep 19, 2011 at 14:58 | answer | added | Joseph O'Rourke | timeline score: 3 | |
| Sep 19, 2011 at 14:32 | comment | added | Steve Huntsman | @Gerhard: the whole point of my desired approach is that it doesn't rely on existence-type arguments as much. As soon as we start talking about "suitable encodings" I might as well resort to the sketch in the third paragraph of my question. | |
| Sep 19, 2011 at 11:58 | answer | added | Carl Mummert | timeline score: 1 | |
| Sep 19, 2011 at 5:35 | comment | added | Gerhard Paseman | You might consider the subproblem (I think Turing may have used this at one point, if not in his 1936 paper) of deciding whether, using a sutiable encoding, if machine M halts given the input of machine M. If there were a program H to decide it, a tweaking of H gives a logical contradiction. Gerhard "Ask Me About System Design" Paseman, 2011.09.18 | |
| Sep 19, 2011 at 4:34 | history | edited | Steve Huntsman | CC BY-SA 3.0 |
added 9 characters in body
|
| Sep 19, 2011 at 4:28 | history | asked | Steve Huntsman | CC BY-SA 3.0 |