Timeline for The Halting Problem and Church's Thesis
Current License: CC BY-SA 3.0
18 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| S Sep 12, 2016 at 1:43 | history | bounty ended | Frode Alfson Bjørdal | ||
| S Sep 12, 2016 at 1:43 | history | notice removed | Frode Alfson Bjørdal | ||
| Sep 8, 2016 at 15:24 | answer | added | Timothy Chow | timeline score: 4 | |
| Sep 8, 2016 at 15:05 | vote | accept | Frode Alfson Bjørdal | ||
| Sep 8, 2016 at 1:02 | answer | added | Joel David Hamkins | timeline score: 13 | |
| Sep 7, 2016 at 22:35 | history | edited | Frode Alfson Bjørdal | CC BY-SA 3.0 |
Parenthetical
|
| S Sep 7, 2016 at 22:14 | history | bounty started | Frode Alfson Bjørdal | ||
| S Sep 7, 2016 at 22:14 | history | notice added | Frode Alfson Bjørdal | Canonical answer required | |
| Sep 7, 2016 at 22:11 | history | edited | Frode Alfson Bjørdal | CC BY-SA 3.0 |
Style
|
| Aug 28, 2016 at 13:56 | vote | accept | Frode Alfson Bjørdal | ||
| Aug 28, 2016 at 13:56 | |||||
| Aug 19, 2016 at 21:02 | history | edited | Andrés E. Caicedo | CC BY-SA 3.0 |
added 7 characters in body
|
| Aug 19, 2016 at 15:33 | comment | added | Jason Rute | (continued) Moreover, I don't think applications of Church's thesis are all that informal. While constructing the Turing machine would be a mess, in most cases proving that such a desired Turing machine exists would only involve a few lemmas showing that basic operations are doable in a Turing machine. (Unbounded search can do a lot!) Many books don't even start invoking Church's thesis until they have given lots of results convincing the reader that a number of very general computational patterns can be formalized. | |
| Aug 19, 2016 at 15:25 | comment | added | Jason Rute | I think it should be mentioned that this light hand-waving is not unique to computability theory. Lots of areas of mathematics containing phrasing like "we leave the standard details to the reader" or "by a routine argument". Computability theory just gives it a name. | |
| Aug 19, 2016 at 11:44 | comment | added | Wojowu | The thing is about how you define "solvable". Church's thesis states that if you were to use the informal notion of "solvable", then it is exactly the same as the notion of "solvable by a Turing machine", and the proof then follows. However, if we want to prove this formally, then we need a precise notion of "solvable", and the most popular choice is then "there is a Turing machine..." one. If you adapt this definition, Church's thesis is avoided. | |
| Aug 19, 2016 at 11:39 | answer | added | Aryeh Kontorovich | timeline score: 6 | |
| Aug 19, 2016 at 10:39 | answer | added | Andrej Bauer | timeline score: 20 | |
| Aug 19, 2016 at 10:27 | comment | added | Burak | It can be. The question is whether you are willing to construct a Turing machine (with possibly dozens of states) to carry out the procedure that is given in the proof. Most of the time, people choose to describe algorithms informally and invoke the Church-Turing thesis to handle the "dirty work" that is needed to be done. (Because the Church-Turing thesis is obviously true!). | |
| Aug 19, 2016 at 10:18 | history | asked | Frode Alfson Bjørdal | CC BY-SA 3.0 |