Timeline for The Halting Problem and Church's Thesis
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 8, 2016 at 20:34 | comment | added | Joel David Hamkins | Well, let's call it scomputation then. The question is whether our physical universe allows for these scomputational procedures or not, and the strong CTT says that it does not. And it is that for which I am claiming we have only weak evidence. It seems to me that the question is one of physics, rather than mathematics or philosophy. The issue of whether they are sufficiently finitary for you or not seems beside the point. | |
| Sep 8, 2016 at 20:22 | comment | added | Timothy Chow | I wouldn't argue that the strong CTT is true by definition, but I would argue that to deserve the name "computation" (as used in the CTT, strong or weak) there needs to be some kind of finiteness condition (not necessarily "in the Turing manner" though), which every hypercomputation proposal I have seen blatantly violates. But this is not the place to spell out the argument in detail. | |
| Sep 8, 2016 at 18:07 | comment | added | Joel David Hamkins | If it is just a question of terminology, then one can of course use another word. But I would say that the point of the discussion is the possibility, true or not, that there may be these other physical computation-like procedures that we cannot verify in the Turing manner by a finitary procedure. I would find it inadequate to say that the strong CTT is true simply by the definition of the term, "computation." Meanwhile, I would add that we do use the word more generally, as in oracle computations, BSS computations, ITTM computations and in higher recursion theory. It is a metaphorical use. | |
| Sep 8, 2016 at 15:56 | comment | added | Timothy Chow | Regarding your remark that "We don't actually have much reason to think that it should not be possible in principle to take advantage of them for computational effect," I believe that we do have good reasons to refuse to use the word "computation" to refer to such "hypercomputational" proposals whose results cannot be confirmed by any kind of finitary procedure, even in principle. I've discussed this on the Foundations of Mathematics mailing list at some length. | |
| Sep 8, 2016 at 15:05 | vote | accept | Frode Alfson Bjørdal | ||
| Sep 8, 2016 at 15:05 | comment | added | Frode Alfson Bjørdal | Many thanks! I like the comprehensive nature of your answer and its fine distinction between the weak and the strong CTT. I will accept it, though that is not intended as a detriment to other answers. Some of this on CTT that you mention I remember from ages ago in connection with literature I read on AI. As you know, László Kalmár, expressed skepticism concerning CTT, as did a Polish philosopher Leon Gumański; Jan Woleński expressed in conversation many years ago that it was a scandal that Gumanski did not understand the diagonal argument. | |
| Sep 8, 2016 at 1:12 | history | edited | Joel David Hamkins | CC BY-SA 3.0 |
added 180 characters in body
|
| Sep 8, 2016 at 1:02 | history | answered | Joel David Hamkins | CC BY-SA 3.0 |