Timeline for The Halting Problem and Church's Thesis
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 28, 2016 at 14:23 | comment | added | Frode Alfson Bjørdal | Thanks! On p. 25 with the \textit{More formal proof}, it is the step summed up with the sentence \quote{By Church's Thesis, \psi is partial recursive} which worried me; as in the informal version, the premise is that there is an algorithm for \psi. Is it that a Turing machine may show that the function \psi would be partial recursive, where $\psi(z,x)=(1 \ if \ \phi_z(x,x)=0; divergent \ if \ \phi_z(x,x)\neq 0 \ or \ divergent)$ and \phi is partial recursive? | |
| Aug 28, 2016 at 13:56 | vote | accept | Frode Alfson Bjørdal | ||
| Aug 28, 2016 at 13:56 | |||||
| Aug 28, 2016 at 11:25 | comment | added | Andrej Bauer | Read Roger's reference to Church's thesis as a phrase whose meaning is "we could do the following in terms of Turing machines but it would be very painful, so let's be a bit informal". It's not a real reference to the real Church's thesis. That's how I understand it. I envy a bit that you took classes from Church himself. I am his academic grandson but I never met him. | |
| Aug 27, 2016 at 21:37 | comment | added | Frode Alfson Bjørdal | I also associate myself to no church on the matter, although I had Church as a teacher; in the spring of 1989 - as he turned 86 - I took his last graduate seminary in logic at UCLA, with an oral exam at the end. It seemed to me that Rogers' account inaccurately assigns Curch's Thesis a more prominent role than necessary in the proof of Theorem VII. But at this point I am confused, and I wonder about how to unconfuse myself. | |
| Aug 19, 2016 at 20:52 | history | edited | Andrej Bauer | CC BY-SA 3.0 |
added 114 characters in body
|
| Aug 19, 2016 at 10:39 | history | answered | Andrej Bauer | CC BY-SA 3.0 |